Find Greatest Common Divisor of Array (LeetCode 1979)
You will see how Euclid's remainder step finds the greatest common divisor of the smallest and largest value in a few steps.
You get an array of positive integers, nums. Take its smallest value and its largest value, and return their greatest common divisor: the largest positive integer that divides both of them with no remainder.
Only those two values matter; the other values of nums play no part in the answer. When the smallest and the largest value are equal, as in [3,3], the answer is that value itself.
Worked Examples
nums = [2,5,6,9,10]2nums = [7,5,6,8,3]1nums = [3,3]3⚖️Formal Constraints & Bounds
2 <= nums.length <= 10001 <= nums[i] <= 1000
Why It Works & Core Invariant
a % b is a minus a multiple of b, so the pairs (a, b) and (b, a % b) have exactly the same common divisors. Repeating the step shrinks the pair fast until b is 0, and then a is the greatest common divisor.
Real-World Scenario & Production Applications
Reducing a ratio to lowest terms: an image editor showing a 1920 x 1080 screen as 16:9, or a recipe tool scaling 12 eggs to 18 cups of flour down to 2:3, divides both numbers by their greatest common divisor.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []Step-by-Step Execution Trace Table
Example 2, nums = [7,5,6,8,3]:
| Step | Line | a | b | Why |
|---|---|---|---|---|
| 1 | lo, hi = min(nums), max(nums) | lo = 3, hi = 8: only the two ends count | ||
| 2 | gcd(hi, lo) | 8 | 3 | The call starts with the larger value first |
| 3 | a, b = b, a % b | 3 | 2 | 8 % 3 = 2, computed from the old a |
| 4 | a, b = b, a % b | 2 | 1 | 3 % 2 = 1 |
| 5 | a, b = b, a % b | 1 | 0 | 2 % 1 = 0 |
| 6 | return a | 1 | 0 | b is 0, so a = 1 is the answer |
With a = b first and b = a % b second, step 3 would compute 3 % 3 = 0 and return 3.
| 1 | The pairs `(a, b)` and `(b, a % b)` have the same common divisors, and `gcd(a, 0)` is `a`: shrink the pair until `b` is 0. |
| 2 | Keep this true: `gcd(a, b)` is the same at every step, and `b` gets smaller every step. |
| 3 | Reduce `nums` to two numbers; then loop while the second number of the pair is not 0, replacing the pair each time; the answer is one of the two when the loop ends. |
| 4 | The trap: update `a` and `b` in one statement. `a = b` first makes `b = a % b` compute `b % b`, always 0, and the loop returns the smaller value. |
Target: Find Greatest Common Divisor of Array (LeetCode 1979). The problem asks for the gcd of the smallest and largest value, so one pass each finds them and the rest of `nums` is ignored.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The obvious way to find the greatest common divisor is trial division: try lo, then lo - 1, and so on, until a number divides both values. That can take as many steps as the smaller value. Euclid's GCD never tries a candidate. It replaces the pair (a, b) with (b, a % b), a smaller pair with exactly the same common divisors, and stops when b is 0: then a is the answer. find_gcd only needs the two ends of nums, so it finds lo and hi and returns gcd(hi, lo).
🧱 The Analogy: Tiling a Floor With the Biggest Square
You want to cover a 8 x 3 floor with equal square tiles, as large as possible. Lay down 3 x 3 squares along the long side: two fit, and a 2 x 3 strip is left over. Whatever square tiles the whole floor must also tile that leftover strip, and the other way round, so the problem is now the 3 x 2 strip. One 2 x 2 square leaves a 1 x 2 strip, and 1 x 1 squares fill it exactly. The biggest square is 1 x 1, found in three cuts instead of trying every size. Each cut is one a % b.
🪄 The Mathematical Harmony / Magic Trick
while b: a, b = b, a % breturn a a % b equals a - q * b for some whole number q. A number that divides a and b divides a - q * b; a number that divides b and a - q * b divides a. So gcd(a, b) == gcd(b, a % b) at every step, and when b reaches 0, gcd(a, 0) is simply a. The remainder is also small: whenever a >= b, a % b is less than half of a, so every two steps at least halve the pair. The one line that must be exact is the update: both new values come from the old pair, so a, b = b, a % b is a single statement.
💡 Summary
Find lo and hi, then loop a, b = b, a % b while b is not 0 and return a. for the two ends plus remainder steps, extra space.
Updating one value at a time: write
a, b = b, a % bin one statement.a = bfollowed byb = a % bcomputesb % b == 0, sogcd(8, 3)returns 3 instead of 1.Returning the wrong value: loop
while b:andreturn a. The pair ends as(g, 0), soreturn balways gives 0.Subtracting instead of taking the remainder:
a - bagain and again takesa / bsteps (about 10^9 forgcd(109, 1));%needs at most about 2 log2 of the smaller value.The gcd of the wrong values: here it is
min(nums)andmax(nums)only. In[2,5,6,9,10]the answer is 2, while the gcd of all five values is 1.
4-Phase Thought Process Model
You will see how a senior engineer hears "greatest common divisor" and reaches for Euclid, not trial division.
Pattern Recognition Signals
The 10-second spot
"Take its smallest value and its largest value", "return their greatest common divisor" and "the largest positive integer that divides both of them with no remainder": a common divisor of two whole numbers. That is the signal for Euclid's GCD: replace the pair by (b, a % b) until b is 0, instead of trying every divisor.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
gcd(a, b) is the same before and after every a, b = b, a % b, and b gets smaller each time; when b is 0, a is the greatest common divisor of hi and lo.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Update both values in one statement,
a, b = b, a % b:a = bfirst makesb = a % bcomputeb % b == 0, sogcd(8, 3)for[7,5,6,8,3]returns 3 instead of 1.Only
min(nums)andmax(nums)count: the gcd of every value of[2,5,6,9,10]is 1, but the answer is 2.Loop
while b:andreturn a: the pair ends as(g, 0), soreturn bis always 0.Use
%, not repeated subtraction: subtracting takesa / bsteps, fine at 1000 but about 10^9 steps when values reach 10^9.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Euclid's GCD. The problem only cares about the smallest and the largest value, so I find them in one pass each and run Euclid's algorithm on that pair. The idea is that a and b have exactly the same common divisors as b and a mod b, because a mod b is a minus a multiple of b. So I keep replacing the pair with b and a mod b until b is zero, and then a is the answer. The numbers at least halve every two steps, so the loop is logarithmic. The trap is the update: I write a comma b equals b comma a mod b as one statement, because setting a to b first would compute b mod b, which is always zero, and I'd return the smaller number. That's O(N plus log M) time and
O(1)extra space.
So: find lo and hi, loop a, b = b, a % b until b is 0, and return a.
Complexity & Mathematical Proof
O(N + log M)
min(nums) and max(nums) each read the N values once: O(N). Then gcd(hi, lo) runs while b:. Each step does one % and one swap. Whenever a >= b, a % b is less than half of a (if b <= a / 2 the remainder is below b; otherwise it is a - b, below a / 2), and two steps turn the pair's first value a into a % b. So the first value at least halves every two steps, and the loop runs at most about 2 * log2(M) times: O(log M). Total: O(N + log M).
O(1)
find_gcd keeps lo and hi; gcd keeps a and b and loops instead of recursing, so no call stack grows: O(1). The answer is one integer.
T(N, M) = 2N (min and max) + 2 · log2(M) (remainder steps) = O(N + log M)
min(nums) and max(nums) each read the N values once: O(N). Then gcd(hi, lo) runs while b:. Each step does one % and one swap. Whenever a >= b, a % b is less than half of a (if b <= a / 2 the remainder is below b; otherwise it is a - b, below a / 2), and two steps turn the pair's first value a into a % b. So the first value at least halves every two steps, and the loop runs at most about 2 * log2(M) times: O(log M). Total: O(N + log M).
Derivation Progression
O(N)
min(nums) and max(nums) each read every value once.
O(1)
a, b = b, a % b is one % and one swap.
O(log M)
Whenever a >= b, a % b < a / 2, and two steps turn a into a % b, so a at least halves every two steps.
O(N + log M)
One pass for the ends, then a logarithmic number of constant-time steps.
Variable Definitions
Number of values, len(nums) (at most 1000)
The largest value, max(nums) (at most 1000)
Memory Architecture & Bounds
O(1): gcd loops instead of recursing
O(1): lo, hi, a, b
O(1): one integer
Boundary Best / Worst Cases
: lo divides hi, so one remainder step ends the loop
: consecutive Fibonacci numbers such as 610 and 987 take the most steps (14)
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "greatest common divisor", "the largest positive integer that divides both of them", "take its smallest value and its largest value". Two whole numbers and their largest shared divisor: Euclid's GCD, a, b = b, a % b until b is 0.
At most values, each at most : min and max are reads, and Euclid on two values up to takes at most remainder steps (consecutive Fibonacci numbers, and ). Trial division would need up to checks here, and for values up to .
With huge integers, as in cryptography, each % is itself a long division, so libraries use binary GCD or Lehmer's variant to cut its cost. With negative inputs, languages disagree on the sign of % (in Python it follows the divisor, in C and Java the dividend), so take absolute values first. A recursive gcd costs one stack frame per step; the loop never overflows.
Core Algorithmic State Invariants
`a % b` is `a` minus a multiple of `b`, so `(a, b)` and `(b, a % b)` have exactly the same common divisors; `gcd(a, 0)` is `a`, the answer.
`a, b = b, a % b` computes both new values from the old pair. Setting `a = b` first turns the remainder into `b % b == 0` and ends the loop with the wrong value.
Whenever `a >= b`, `a % b < a / 2`, so the pair at least halves every two steps: O(log M) steps after the O(N) pass for `lo` and `hi`, O(1) space.
Find Greatest Common Divisor of Array (LeetCode 1979)
You will see how Euclid's remainder step finds the greatest common divisor of the smallest and largest value in a few steps.
You get an array of positive integers, nums. Take its smallest value and its largest value, and return their greatest common divisor: the largest positive integer that divides both of them with no remainder.
Only those two values matter; the other values of nums play no part in the answer. When the smallest and the largest value are equal, as in [3,3], the answer is that value itself.
Worked Examples
nums = [2,5,6,9,10]2nums = [7,5,6,8,3]1nums = [3,3]3⚖️Formal Constraints & Bounds
2 <= nums.length <= 10001 <= nums[i] <= 1000
Why It Works & Core Invariant
a % b is a minus a multiple of b, so the pairs (a, b) and (b, a % b) have exactly the same common divisors. Repeating the step shrinks the pair fast until b is 0, and then a is the greatest common divisor.
Real-World Scenario & Production Applications
Reducing a ratio to lowest terms: an image editor showing a 1920 x 1080 screen as 16:9, or a recipe tool scaling 12 eggs to 18 cups of flour down to 2:3, divides both numbers by their greatest common divisor.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []Step-by-Step Execution Trace Table
Example 2, nums = [7,5,6,8,3]:
| Step | Line | a | b | Why |
|---|---|---|---|---|
| 1 | lo, hi = min(nums), max(nums) | lo = 3, hi = 8: only the two ends count | ||
| 2 | gcd(hi, lo) | 8 | 3 | The call starts with the larger value first |
| 3 | a, b = b, a % b | 3 | 2 | 8 % 3 = 2, computed from the old a |
| 4 | a, b = b, a % b | 2 | 1 | 3 % 2 = 1 |
| 5 | a, b = b, a % b | 1 | 0 | 2 % 1 = 0 |
| 6 | return a | 1 | 0 | b is 0, so a = 1 is the answer |
With a = b first and b = a % b second, step 3 would compute 3 % 3 = 0 and return 3.
| 1 | The pairs `(a, b)` and `(b, a % b)` have the same common divisors, and `gcd(a, 0)` is `a`: shrink the pair until `b` is 0. |
| 2 | Keep this true: `gcd(a, b)` is the same at every step, and `b` gets smaller every step. |
| 3 | Reduce `nums` to two numbers; then loop while the second number of the pair is not 0, replacing the pair each time; the answer is one of the two when the loop ends. |
| 4 | The trap: update `a` and `b` in one statement. `a = b` first makes `b = a % b` compute `b % b`, always 0, and the loop returns the smaller value. |
Target: Find Greatest Common Divisor of Array (LeetCode 1979). The problem asks for the gcd of the smallest and largest value, so one pass each finds them and the rest of `nums` is ignored.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The obvious way to find the greatest common divisor is trial division: try lo, then lo - 1, and so on, until a number divides both values. That can take as many steps as the smaller value. Euclid's GCD never tries a candidate. It replaces the pair (a, b) with (b, a % b), a smaller pair with exactly the same common divisors, and stops when b is 0: then a is the answer. find_gcd only needs the two ends of nums, so it finds lo and hi and returns gcd(hi, lo).
🧱 The Analogy: Tiling a Floor With the Biggest Square
You want to cover a 8 x 3 floor with equal square tiles, as large as possible. Lay down 3 x 3 squares along the long side: two fit, and a 2 x 3 strip is left over. Whatever square tiles the whole floor must also tile that leftover strip, and the other way round, so the problem is now the 3 x 2 strip. One 2 x 2 square leaves a 1 x 2 strip, and 1 x 1 squares fill it exactly. The biggest square is 1 x 1, found in three cuts instead of trying every size. Each cut is one a % b.
🪄 The Mathematical Harmony / Magic Trick
while b: a, b = b, a % breturn a a % b equals a - q * b for some whole number q. A number that divides a and b divides a - q * b; a number that divides b and a - q * b divides a. So gcd(a, b) == gcd(b, a % b) at every step, and when b reaches 0, gcd(a, 0) is simply a. The remainder is also small: whenever a >= b, a % b is less than half of a, so every two steps at least halve the pair. The one line that must be exact is the update: both new values come from the old pair, so a, b = b, a % b is a single statement.
💡 Summary
Find lo and hi, then loop a, b = b, a % b while b is not 0 and return a. for the two ends plus remainder steps, extra space.
Updating one value at a time: write
a, b = b, a % bin one statement.a = bfollowed byb = a % bcomputesb % b == 0, sogcd(8, 3)returns 3 instead of 1.Returning the wrong value: loop
while b:andreturn a. The pair ends as(g, 0), soreturn balways gives 0.Subtracting instead of taking the remainder:
a - bagain and again takesa / bsteps (about 10^9 forgcd(109, 1));%needs at most about 2 log2 of the smaller value.The gcd of the wrong values: here it is
min(nums)andmax(nums)only. In[2,5,6,9,10]the answer is 2, while the gcd of all five values is 1.
4-Phase Thought Process Model
You will see how a senior engineer hears "greatest common divisor" and reaches for Euclid, not trial division.
Pattern Recognition Signals
The 10-second spot
"Take its smallest value and its largest value", "return their greatest common divisor" and "the largest positive integer that divides both of them with no remainder": a common divisor of two whole numbers. That is the signal for Euclid's GCD: replace the pair by (b, a % b) until b is 0, instead of trying every divisor.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
gcd(a, b) is the same before and after every a, b = b, a % b, and b gets smaller each time; when b is 0, a is the greatest common divisor of hi and lo.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Update both values in one statement,
a, b = b, a % b:a = bfirst makesb = a % bcomputeb % b == 0, sogcd(8, 3)for[7,5,6,8,3]returns 3 instead of 1.Only
min(nums)andmax(nums)count: the gcd of every value of[2,5,6,9,10]is 1, but the answer is 2.Loop
while b:andreturn a: the pair ends as(g, 0), soreturn bis always 0.Use
%, not repeated subtraction: subtracting takesa / bsteps, fine at 1000 but about 10^9 steps when values reach 10^9.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Euclid's GCD. The problem only cares about the smallest and the largest value, so I find them in one pass each and run Euclid's algorithm on that pair. The idea is that a and b have exactly the same common divisors as b and a mod b, because a mod b is a minus a multiple of b. So I keep replacing the pair with b and a mod b until b is zero, and then a is the answer. The numbers at least halve every two steps, so the loop is logarithmic. The trap is the update: I write a comma b equals b comma a mod b as one statement, because setting a to b first would compute b mod b, which is always zero, and I'd return the smaller number. That's O(N plus log M) time and
O(1)extra space.
So: find lo and hi, loop a, b = b, a % b until b is 0, and return a.
Complexity & Mathematical Proof
O(N + log M)
min(nums) and max(nums) each read the N values once: O(N). Then gcd(hi, lo) runs while b:. Each step does one % and one swap. Whenever a >= b, a % b is less than half of a (if b <= a / 2 the remainder is below b; otherwise it is a - b, below a / 2), and two steps turn the pair's first value a into a % b. So the first value at least halves every two steps, and the loop runs at most about 2 * log2(M) times: O(log M). Total: O(N + log M).
O(1)
find_gcd keeps lo and hi; gcd keeps a and b and loops instead of recursing, so no call stack grows: O(1). The answer is one integer.
T(N, M) = 2N (min and max) + 2 · log2(M) (remainder steps) = O(N + log M)
min(nums) and max(nums) each read the N values once: O(N). Then gcd(hi, lo) runs while b:. Each step does one % and one swap. Whenever a >= b, a % b is less than half of a (if b <= a / 2 the remainder is below b; otherwise it is a - b, below a / 2), and two steps turn the pair's first value a into a % b. So the first value at least halves every two steps, and the loop runs at most about 2 * log2(M) times: O(log M). Total: O(N + log M).
Derivation Progression
O(N)
min(nums) and max(nums) each read every value once.
O(1)
a, b = b, a % b is one % and one swap.
O(log M)
Whenever a >= b, a % b < a / 2, and two steps turn a into a % b, so a at least halves every two steps.
O(N + log M)
One pass for the ends, then a logarithmic number of constant-time steps.
Variable Definitions
Number of values, len(nums) (at most 1000)
The largest value, max(nums) (at most 1000)
Memory Architecture & Bounds
O(1): gcd loops instead of recursing
O(1): lo, hi, a, b
O(1): one integer
Boundary Best / Worst Cases
: lo divides hi, so one remainder step ends the loop
: consecutive Fibonacci numbers such as 610 and 987 take the most steps (14)
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "greatest common divisor", "the largest positive integer that divides both of them", "take its smallest value and its largest value". Two whole numbers and their largest shared divisor: Euclid's GCD, a, b = b, a % b until b is 0.
At most values, each at most : min and max are reads, and Euclid on two values up to takes at most remainder steps (consecutive Fibonacci numbers, and ). Trial division would need up to checks here, and for values up to .
With huge integers, as in cryptography, each % is itself a long division, so libraries use binary GCD or Lehmer's variant to cut its cost. With negative inputs, languages disagree on the sign of % (in Python it follows the divisor, in C and Java the dividend), so take absolute values first. A recursive gcd costs one stack frame per step; the loop never overflows.
Core Algorithmic State Invariants
`a % b` is `a` minus a multiple of `b`, so `(a, b)` and `(b, a % b)` have exactly the same common divisors; `gcd(a, 0)` is `a`, the answer.
`a, b = b, a % b` computes both new values from the old pair. Setting `a = b` first turns the remainder into `b % b == 0` and ends the loop with the wrong value.
Whenever `a >= b`, `a % b < a / 2`, so the pair at least halves every two steps: O(log M) steps after the O(N) pass for `lo` and `hi`, O(1) space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Reduce the input to the two numbers to take the gcd of | lo, hi = min(nums), max(nums) | The problem asks for the gcd of the smallest and largest value, so one pass each finds them and the rest of `nums` is ignored. |
| Stop when the remainder is 0 | while b: | `gcd(a, 0)` is `a`, so a zero `b` means `a` already holds the answer. |
| Euclid's step, both values at once (the trap) | a, b = b, a % b | The new pair has the same common divisors as the old one; both new values are computed from the old pair before either is stored. |
| Answer | return a
return gcd(hi, lo) | When the loop ends the pair is `(g, 0)`, and `g` is the greatest common divisor of `hi` and `lo`. |