Learning Outcome
After this lesson, you should be able to replace gcd(a,b) with gcd(b,a mod b) until the remainder becomes zero.
Problem Statement
Given two integers a and b, return their greatest common divisor.
| Input | Output | Why |
|---|---|---|
a = 56, b = 98 | 14 | 14 is the largest number that divides both 56 and 98. |
Brute Force Approach
Check every possible divisor from min(a,b) down to 1. This can be slow when numbers are large.
Optimized Approach
Use the identity gcd(a,b) = gcd(b,a mod b). Repeated remainders shrink the numbers quickly.
Exact Pseudocode
while b is not 0:
remainder = a % b
a = b
b = remainder
return absolute value of aReference Code
class Solution:
def gcd(self, a, b):
while b != 0:
a, b = b, a % b
return abs(a)Sample Dry Run
| Step | State | Result |
|---|---|---|
| Start | a = 56, b = 98 | continue |
| Step 1 | 56 % 98 = 56 | a = 98, b = 56 |
| Step 2 | 98 % 56 = 42 | a = 56, b = 42 |
| Finish | 56 % 42 = 14, 42 % 14 = 0 | return 14 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(log min(a,b)) | The Euclidean remainder sequence shrinks quickly. |
| Space | O(1) | Only a few integer variables are stored. |
Edge Cases
- gcd(a,0) is absolute value of a.
- gcd(0,b) is absolute value of b.
- Normalize negative inputs with absolute value at the end.
Interview Checklist
- Use modulo, not repeated subtraction.
- Stop when the second value becomes zero.
- Return the nonzero value as positive.
FAQs
Why does gcd(a,b) equal gcd(b,a mod b)?
Any divisor of a and b also divides the remainder after removing multiples of b.
Why is modulo faster than subtraction?
Modulo removes many repeated subtraction steps in one operation.
What is the core pattern?
Euclidean remainder reduction.