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
Dry Run
Input: a = 12, b = 18
- Initial values:
a = 12, b = 18.
- Compute
a % b = 12 % 18 = 12. Update a = 18, b = 12.
- Compute
a % b = 18 % 12 = 6. Update a = 12, b = 6.
- Compute
a % b = 12 % 6 = 0. Update a = 6, b = 0.
b is 0, return a = 6.
Complexity Analysis
| Operation | Brute Force | Efficient (Euclidean) |
|---|
| Time Complexity | O(min(a, b)) | O(log(min(a, b))) |
| Space Complexity | O(1) | O(1) |
Conclusion
- The brute force approach is simple to implement but inefficient for large numbers due to its O(min(a, b)) time complexity.
- The Euclidean Algorithm optimizes the process by reducing the problem size in each step, achieving O(log(min(a, b))) time complexity.
- This demonstrates the importance of mathematical insights in optimizing algorithms.