Greatest Common Divisor (GCD) Explained

Problem Statement

Given two non-negative integers a and b, find their greatest common divisor (GCD). The GCD is the largest positive integer that divides both numbers without leaving a remainder. This problem often uses Euclid’s algorithm, which is an efficient method based on the principle that GCD(a, b) = GCD(b, a % b).

Example

Input: a = 48, b = 18

Output: 6

Explanation: The divisors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 48, and of 18 are 1, 2, 3, 6, 9, 18. The greatest common divisor is 6.

Code

public class Solution {
    public int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.gcd(48, 18)); // 6
    }
}
            

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Example usage
print(gcd(48, 18))  # 6
            

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Example usage
console.log(gcd(48, 18)); // 6
            

Explanation

• Use Euclid’s algorithm: repeatedly divide a by b and update a and b.
• The remainder becomes the new divisor, and the previous divisor becomes the dividend.
• Continue until the remainder is 0; the last non-zero remainder is the GCD.
• Handle cases where one number is 0 (GCD(a, 0) = a).

Note