Problem Statement
Given two integers, find their greatest common divisor (GCD) using the Euclidean Algorithm.
Example
-
Input: gcd(12, 18)
Output: 6
-
Input: gcd(101, 103)
Output: 1
-
Input: gcd(56, 98)
Output: 14
Brute Force Approach
Approach
Idea: Iterate through all integers from 1 to the smaller of the two numbers. Identify the largest integer that divides both numbers without a remainder.
Steps
- Identify the smaller of the two numbers.
- Iterate from
1 to the smaller number.
- Check if the current number divides both input numbers without a remainder.
- Keep track of the largest such number.
- Return the largest common divisor.
Time & Space Complexity
- Time Complexity: O(min(a, b))
- Iterate up to the smaller number.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: a = 12, b = 18
- Identify the smaller number:
12.
- Check divisors of
12:
1: Divides both, update gcd = 1.2: Divides both, update gcd = 2.3: Divides both, update gcd = 3.6: Divides both, update gcd = 6.
- Return
6.
Efficient Approach Using Euclidean Algorithm
Approach
Idea: The Euclidean Algorithm is based on the principle that the GCD of two numbers a and b is the same as the GCD of b and a % b. This reduces the problem size significantly in each step.
Steps
- If
b is 0, return a as the GCD.
- Otherwise, compute
gcd(b, a % b).
- Repeat until
b becomes 0.
Time & Space Complexity
- Time Complexity: O(log(min(a, b)))
- The size of the problem reduces significantly in each step.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet