4.GCD.md

Find GCD of Two Numbers

📋 Problem Statement

Given two integers N₁ and N₂, compute their Greatest Common Divisor (GCD)—the largest positive integer that divides both without leaving a remainder.

---

🔎 Examples

N₁	N₂	GCD	Explanation
9	12	3	Factors of 9: 1, 3, 9; Factors of 12: 1, 2, 3, 4, 6, 12; Common: 1, 3 → 3 is greatest.
20	15	5	Factors of 20: 1, 2, 4, 5, 10, 20; Factors of 15: 1, 3, 5, 15; Common: 1, 5 → 5 is greatest.
0	7	7	By convention, gcd(0, b) = b.
–8	12	4	We take absolute values: gcd(8, 124).

---

💡 Approach

Euclidean Algorithm (Optimized) Leverages the fact that

$$ \gcd(a, b) = \gcd(b,; a \bmod b) $$

and that $\gcd(a,0)=|a|$.

1. Ensure non-negativity: work with $|a|$ and $|b|$.

2. Iterate until one number becomes 0:

   • Replace the larger by its remainder when divided by the smaller.

3. Result: the non-zero number is the GCD.

---

📝 Algorithm

FUNCTION findGCD(a, b):
    a ← abs(a)
    b ← abs(b)

    WHILE b ≠ 0:
        temp ← b
        b ← a mod b
        a ← temp

    RETURN a

---

💾 C++ Code Snippet

#include <iostream>
#include <cstdlib>     // for std::abs
using namespace std;

// Iterative Euclidean algorithm
int findGCD(int a, int b) {
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        int rem = a % b;
        a = b;
        b = rem;
    }
    return a;
}

int main() {
    int n1, n2;
    cin >> n1 >> n2;

    int gcd = findGCD(n1, n2);
    cout << "GCD of " << n1 << " and " << n2 << " is: " << gcd << endl;
    return 0;
}

Example Run:

Input:  20 15  
Output: GCD of 20 and 15 is: 5

---

📈 Complexity Analysis

• Time Complexity:

  • $O(\log \min(a, b))$.
  • Each modulus operation reduces the pair significantly (in the worst case by the golden-ratio factor).

• Space Complexity:

  • $O(1)$.
  • Only a constant number of variables (a, b, rem, temp).

---

✨ Notes & Variations

• Recursive Version:

  int findGCD(int a, int b) {
      return b == 0 ? abs(a) : findGCD(b, a % b);
  }

• Built-in (C++17):

  #include <numeric>
  int g = std::gcd(n1, n2);

• Edge Cases:

  • One or both inputs zero.
  • Negative inputs (handle via abs).
  • Very large inputs (fits within 32-bit? consider 64-bit types).

---