What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Math & Geometry

P2EasyMental model~2 min speedrun

Euclidean Algorithm (Greatest Common Divisor)

Find Greatest Common Divisor of Array (LC 1979)(opens leetcode.com)

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.

Example 1

Input:nums = [2,5,6,9,10]

Output:2

The smallest value is 2 and the largest is 10. 2 divides 10, so their greatest common divisor is 2. (The five values together only share 1: just the two ends count.)

Euclid's GCD

two numbers ➔ replace (a, b) by (b, a % b) ➔ greatest common divisor

Spot it when: Several whole numbers or lengths must share a divisor: the largest number that divides them all, a block or period two things are both made of, groups of equal size, or a fraction in lowest terms.

Euclid's GCD

Python

1	def gcd(a: int, b: int) -> int:
2	"""Euclid's algorithm: gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a."""
3	# 1. Replace the Pair Until It Shrinks to Zero (the trap):
4	# a % b is a minus a multiple of b, so a number dividing both a and b also divides a % b, and a
5	# number dividing b and a % b also divides a: both values must update from the old pair at once.
6	while b:
7	a, b = b, a % b
8	# 2. Return the Answer:
9	# The loop stops once b is 0; since gcd(a, 0) == a, a now holds the greatest common divisor.
10	return a
11
12
13	def find_gcd(nums: list[int]) -> int:
14	"""Find Greatest Common Divisor of Array: Euclid's algorithm on the smallest and largest value.
15	Time: O(N + log M) \| Space: O(1)
16	"""
17	lo, hi = min(nums), max(nums) # lo, hi: the two ends; only they matter, the other values play no part
18	return gcd(hi, lo)

Invariant: gcd(a, b) never changes from one loop step to the next, and b shrinks every step; when b is 0, a is the greatest common divisor.

Euclid's algorithm finds the greatest common divisor of two numbers by replacing the pair (a, b) with (b, a % b) until b is 0; then a is the answer. Here find_gcd only needs the smallest and largest value, lo and hi, so it returns gcd(hi, lo). It is correct because a % b is a minus a multiple of b: any number that divides both a and b also divides a % b, and any number that divides b and a % b also divides a, so the pair changes but its common divisors never do. The trap is the update: write a, b = b, a % b as one statement. Updating a = b first makes the next line compute b % b, which is always 0, so the loop stops after one step and returns the smaller number.

See it run

Euclid's GCD, step by step

a 8b 3

Each row is one pair (a, b) the loop sees, and the remainder a % b that makes the next row.

read the starting pair (a, b)
remainder the value of a % b for this pair
new pair the pair after a, b = b, a % b
answer a when b is 0: the greatest common divisor

lo, hi = 3, 8. find_gcd returns gcd(8, 3), so the loop starts with a = 8 and b = 3.

pair 0

8read

3read

pair 1

pair 2

pair 3

1 / 9

Gotchas1 of 4

The trap
Gotcha 1: Writing a = b and then b = a % b
Mistake
```
a = b
b = a % b
```
Fix
```
a, b = b, a % b
```
What happens: After a = b, the old a is gone. The next line computes b % b, which is always 0. The loop stops after one step and returns the old b. So gcd(8, 3) returns 3 instead of 1.
Example: a = 8, b = 3
Mistake: returns 3Fix: returns 1
Gotcha 2: Returning b instead of a after the loop
Mistake
```
return b
```
Fix
```
return a
```
What happens: The loop stops when b is 0, so the pair ends as (g, 0). return b then always returns 0. The rule gcd(x, 0) == x also lets a running gcd start from 0, as in Number of Subarrays With GCD Equal to K (LC 2447).
Example: a = 8, b = 3
Mistake: returns 0Fix: returns 1
Gotcha 3: Using repeated subtraction instead of %
Mistake
```
while b:
    if a >= b:
        a -= b
    else:
        a, b = b, a
```
Fix
```
while b:
    a, b = b, a % b
```
What happens: Subtraction gives the same answer, but it can take a / b steps. For gcd(10**9, 1), that is about 10^9 steps. With %, the number of steps is at most about 2 * log2 of the smaller value.
Gotcha 4: Taking the gcd of all values in nums
Mistake
```
return functools.reduce(gcd, nums)
```
Fix
```
lo, hi = min(nums), max(nums)
return gcd(hi, lo)
```
What happens: Find Greatest Common Divisor of Array (LC 1979) asks for the gcd of only the smallest and the largest value. For [2, 5, 6, 9, 10], that is the gcd of 10 and 2, which is 2. The gcd of all five values is 1. Other problems do take the gcd of every value, such as X of a Kind in a Deck of Cards (LC 914) with its counts.
Example: nums = [2, 5, 6, 9, 10]
Mistake: returns 1Fix: returns 2

Not this one if…

Switch to Canonical Key when the gcd only puts each item into a standard form and the question is how many items share that form, as in Max Points on a Line (LC 149). See Canonical Key

Deep Dive

Why gcd(a, b) equals gcd(b, a % b)

The greatest common divisor (gcd) of two numbers is the largest number that divides both. Euclid's rule says gcd(a, b) == gcd(b, a % b).

Write a = q * b + r, where r = a % b. Then r = a - q * b. Let d divide both a and b. Then d divides a - q * b, so d divides r. Now let d divide both b and r. Then d divides q * b + r, which is a.

So the pair (a, b) and the pair (b, r) have exactly the same common divisors. The largest one is the same, which means the gcd does not change.

The base case is gcd(a, 0) == a, because every number divides 0 and a is the largest divisor of a.

Why the loop ends fast

The remainder a % b is always smaller than b. So b shrinks every step, and it can only reach 0.

It shrinks quickly. After two steps, the larger value is at most half of what it was. So the number of steps is at most about 2 * log2 of the smaller value. The slowest inputs are consecutive Fibonacci numbers: gcd(832040, 514229) takes 28 steps, and gcd(10**9, 1) takes one.

Repeated subtraction gives the same answer, but gcd(10**9, 1) would take about 10^9 steps. The % operator removes many subtractions at once.

Trace for find_gcd([7, 5, 6, 8, 3]): the answer is 1

Find Greatest Common Divisor of Array (LC 1979) asks for the gcd of the smallest and the largest value only. Here lo = 3 and hi = 8. The other values do not matter, so find_gcd returns gcd(8, 3).

Pair (8, 3): 8 % 3 = 2, so the next pair is (3, 2). Pair (3, 2): 3 % 2 = 1, so the next pair is (2, 1). Pair (2, 1): 2 % 1 = 0, so the next pair is (1, 0). Now b is 0 and a = 1 is the answer.

The tuple assignment a, b = b, a % b computes the right side from the old pair, and then assigns both names. If the code wrote a = b first, the next line would compute b % b, which is 0. For (8, 3), the loop would stop at once and return 3, which is wrong.

The other examples of Find Greatest Common Divisor of Array (LC 1979) also work. For [2, 5, 6, 9, 10], the pair is (10, 2), 10 % 2 = 0, and the answer is 2. For [3, 3], the answer is 3.

Cost and where the gcd shows up

gcd takes O(log M) time and O(1) space, where M is the smaller input. find_gcd also scans the array once for min and max, so it takes O(N + log M) time in total.

A gcd of many numbers is built pair by pair, because gcd(a, b, c) == gcd(gcd(a, b), c). A running gcd can start at 0, because gcd(0, x) == x. This is how Number of Subarrays With GCD Equal to K (LC 2447) keeps a gcd as the subarray grows.

Other problems use the same loop. X of a Kind in a Deck of Cards (LC 914) takes the gcd of all the value counts. Greatest Common Divisor of Strings (LC 1071) uses the gcd of the two lengths. Check If It Is a Good Array (LC 1250) asks whether the gcd of all numbers is 1.

When the gcd only turns each item into a standard form, as in Max Points on a Line (LC 149), the question is how many items share the form. That is the Canonical Key card.

60-Second Pitch

"Euclid's rule says gcd(a, b) == gcd(b, a % b). The remainder is a minus a multiple of b, so any number that divides both a and b also divides the remainder, and the reverse is also true. The common divisors do not change. I loop while b is not 0 and write a, b = b, a % b as one statement. When b is 0, gcd(a, 0) is a, so I return a. b shrinks every step, and the number of steps is about 2 * log2 of the smaller value. So the time is O(log M) and the space is O(1). For Find Greatest Common Divisor of Array, I take min(nums) and max(nums), so the total time is O(N + log M)."

Common Questions

Why is gcd(a, b) equal to gcd(b, a % b)?: Write a = q * b + r. A number that divides a and b divides a - q * b, which is r. A number that divides b and r divides q * b + r, which is a. So both pairs have the same common divisors, and the largest one is the same.
What is the time complexity?: O(log M), where M is the smaller input. The larger value at least halves every two steps. The worst case is two consecutive Fibonacci numbers: gcd(832040, 514229) takes 28 steps.
Why write a, b = b, a % b as one statement?: Python computes the right side from the old a and b before it assigns either name. Two separate lines, a = b and then b = a % b, compute b % b = 0 on the second line. The loop then ends after one step with the wrong value.
How do you find the gcd of a whole array?: Fold it: g = 0, then g = gcd(g, x) for each x. This works because gcd(0, x) == x. Note that Find Greatest Common Divisor of Array (LC 1979) is different: it asks for the gcd of the smallest and the largest value only.
How do you get the least common multiple (LCM)?: Use lcm(a, b) = a // gcd(a, b) * b. Divide first to keep the intermediate value small. For a = 4 and b = 6, the gcd is 2 and the lcm is 12.

SWE Reasoning

Spot it

The problem asks for the largest number that divides several numbers (Find Greatest Common Divisor of Array (LC 1979)).
Two things must be cut into pieces of the same length, or share a period (Greatest Common Divisor of Strings (LC 1071)).
Items must form groups of one equal size, or all values must be reachable by integer steps (X of a Kind in a Deck of Cards (LC 914), Check If It Is a Good Array (LC 1250)).
A fraction or a direction must be reduced to lowest terms (Max Points on a Line (LC 149)).

The invariant, step by step

The pair is (a, b). Its gcd is some number g.
a % b equals a minus a multiple of b. So the common divisors of (a, b) are exactly the common divisors of (b, a % b).
a, b = b, a % b replaces the pair, and the gcd stays g.
a % b < b, so b gets smaller every step.
b cannot go below 0, so it reaches 0. At that point the pair is (g, 0).
gcd(g, 0) == g, so the loop returns a.

Traps

a = b then b = a % b. The second line computes b % b = 0. gcd(8, 3) returns 3 instead of 1.
return b after the loop. The loop ends when b is 0, so return b always returns 0.
Repeated subtraction. The answer is right, but gcd(10**9, 1) takes about 10^9 steps. Use %.
The gcd of all values in nums. Find Greatest Common Divisor of Array (LC 1979) uses only the minimum and the maximum. For [2, 5, 6, 9, 10], the answer is 2, but the gcd of all five values is 1.
Wrong base case for a running gcd. Start from 0, not 1. gcd(0, x) is x, while gcd(1, x) is always 1.

Practice

Canonical LeetCode:Find Greatest Common Divisor of Array (LC 1979)Greatest Common Divisor of Strings (LC 1071)X of a Kind in a Deck of Cards (LC 914)Number of Subarrays With GCD Equal to K (LC 2447)Check If It Is a Good Array (LC 1250)

Theory Context•Math & Geometry

P2EasyMental model~2 min speedrun

Euclidean Algorithm (Greatest Common Divisor)

Find Greatest Common Divisor of Array (LC 1979)(opens leetcode.com)

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.

Example 1

Input:nums = [2,5,6,9,10]

Output:2

The smallest value is 2 and the largest is 10. 2 divides 10, so their greatest common divisor is 2. (The five values together only share 1: just the two ends count.)

Euclid's GCD

two numbers ➔ replace (a, b) by (b, a % b) ➔ greatest common divisor

Euclid's GCD

Python

1	def gcd(a: int, b: int) -> int:
2	"""Euclid's algorithm: gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a."""
3	# 1. Replace the Pair Until It Shrinks to Zero (the trap):
4	# a % b is a minus a multiple of b, so a number dividing both a and b also divides a % b, and a
5	# number dividing b and a % b also divides a: both values must update from the old pair at once.
6	while b:
7	a, b = b, a % b
8	# 2. Return the Answer:
9	# The loop stops once b is 0; since gcd(a, 0) == a, a now holds the greatest common divisor.
10	return a
11
12
13	def find_gcd(nums: list[int]) -> int:
14	"""Find Greatest Common Divisor of Array: Euclid's algorithm on the smallest and largest value.
15	Time: O(N + log M) \| Space: O(1)
16	"""
17	lo, hi = min(nums), max(nums) # lo, hi: the two ends; only they matter, the other values play no part
18	return gcd(hi, lo)

Invariant: gcd(a, b) never changes from one loop step to the next, and b shrinks every step; when b is 0, a is the greatest common divisor.

See it run

Euclid's GCD, step by step

a 8b 3

Each row is one pair (a, b) the loop sees, and the remainder a % b that makes the next row.

read the starting pair (a, b)
remainder the value of a % b for this pair
new pair the pair after a, b = b, a % b
answer a when b is 0: the greatest common divisor

lo, hi = 3, 8. find_gcd returns gcd(8, 3), so the loop starts with a = 8 and b = 3.

pair 0

8read

3read

pair 1

pair 2

pair 3

1 / 9

Gotchas1 of 4

The trap
Gotcha 1: Writing a = b and then b = a % b
Mistake
```
a = b
b = a % b
```
Fix
```
a, b = b, a % b
```
What happens: After a = b, the old a is gone. The next line computes b % b, which is always 0. The loop stops after one step and returns the old b. So gcd(8, 3) returns 3 instead of 1.
Example: a = 8, b = 3
Mistake: returns 3Fix: returns 1
Gotcha 2: Returning b instead of a after the loop
Mistake
```
return b
```
Fix
```
return a
```
What happens: The loop stops when b is 0, so the pair ends as (g, 0). return b then always returns 0. The rule gcd(x, 0) == x also lets a running gcd start from 0, as in Number of Subarrays With GCD Equal to K (LC 2447).
Example: a = 8, b = 3
Mistake: returns 0Fix: returns 1
Gotcha 3: Using repeated subtraction instead of %
Mistake
```
while b:
    if a >= b:
        a -= b
    else:
        a, b = b, a
```
Fix
```
while b:
    a, b = b, a % b
```
What happens: Subtraction gives the same answer, but it can take a / b steps. For gcd(10**9, 1), that is about 10^9 steps. With %, the number of steps is at most about 2 * log2 of the smaller value.
Gotcha 4: Taking the gcd of all values in nums
Mistake
```
return functools.reduce(gcd, nums)
```
Fix
```
lo, hi = min(nums), max(nums)
return gcd(hi, lo)
```
What happens: Find Greatest Common Divisor of Array (LC 1979) asks for the gcd of only the smallest and the largest value. For [2, 5, 6, 9, 10], that is the gcd of 10 and 2, which is 2. The gcd of all five values is 1. Other problems do take the gcd of every value, such as X of a Kind in a Deck of Cards (LC 914) with its counts.
Example: nums = [2, 5, 6, 9, 10]
Mistake: returns 1Fix: returns 2

Not this one if…

Switch to Canonical Key when the gcd only puts each item into a standard form and the question is how many items share that form, as in Max Points on a Line (LC 149). See Canonical Key

Deep Dive

Why gcd(a, b) equals gcd(b, a % b)

The greatest common divisor (gcd) of two numbers is the largest number that divides both. Euclid's rule says gcd(a, b) == gcd(b, a % b).

So the pair (a, b) and the pair (b, r) have exactly the same common divisors. The largest one is the same, which means the gcd does not change.

The base case is gcd(a, 0) == a, because every number divides 0 and a is the largest divisor of a.

Why the loop ends fast

The remainder a % b is always smaller than b. So b shrinks every step, and it can only reach 0.

Repeated subtraction gives the same answer, but gcd(10**9, 1) would take about 10^9 steps. The % operator removes many subtractions at once.

Trace for find_gcd([7, 5, 6, 8, 3]): the answer is 1

The other examples of Find Greatest Common Divisor of Array (LC 1979) also work. For [2, 5, 6, 9, 10], the pair is (10, 2), 10 % 2 = 0, and the answer is 2. For [3, 3], the answer is 3.

Cost and where the gcd shows up

gcd takes O(log M) time and O(1) space, where M is the smaller input. find_gcd also scans the array once for min and max, so it takes O(N + log M) time in total.

When the gcd only turns each item into a standard form, as in Max Points on a Line (LC 149), the question is how many items share the form. That is the Canonical Key card.

60-Second Pitch

Common Questions

Why is gcd(a, b) equal to gcd(b, a % b)?: Write a = q * b + r. A number that divides a and b divides a - q * b, which is r. A number that divides b and r divides q * b + r, which is a. So both pairs have the same common divisors, and the largest one is the same.
What is the time complexity?: O(log M), where M is the smaller input. The larger value at least halves every two steps. The worst case is two consecutive Fibonacci numbers: gcd(832040, 514229) takes 28 steps.
Why write a, b = b, a % b as one statement?: Python computes the right side from the old a and b before it assigns either name. Two separate lines, a = b and then b = a % b, compute b % b = 0 on the second line. The loop then ends after one step with the wrong value.
How do you find the gcd of a whole array?: Fold it: g = 0, then g = gcd(g, x) for each x. This works because gcd(0, x) == x. Note that Find Greatest Common Divisor of Array (LC 1979) is different: it asks for the gcd of the smallest and the largest value only.
How do you get the least common multiple (LCM)?: Use lcm(a, b) = a // gcd(a, b) * b. Divide first to keep the intermediate value small. For a = 4 and b = 6, the gcd is 2 and the lcm is 12.

SWE Reasoning

Spot it

The problem asks for the largest number that divides several numbers (Find Greatest Common Divisor of Array (LC 1979)).
Two things must be cut into pieces of the same length, or share a period (Greatest Common Divisor of Strings (LC 1071)).
Items must form groups of one equal size, or all values must be reachable by integer steps (X of a Kind in a Deck of Cards (LC 914), Check If It Is a Good Array (LC 1250)).
A fraction or a direction must be reduced to lowest terms (Max Points on a Line (LC 149)).

The invariant, step by step

The pair is (a, b). Its gcd is some number g.
a % b equals a minus a multiple of b. So the common divisors of (a, b) are exactly the common divisors of (b, a % b).
a, b = b, a % b replaces the pair, and the gcd stays g.
a % b < b, so b gets smaller every step.
b cannot go below 0, so it reaches 0. At that point the pair is (g, 0).
gcd(g, 0) == g, so the loop returns a.

Traps

a = b then b = a % b. The second line computes b % b = 0. gcd(8, 3) returns 3 instead of 1.
return b after the loop. The loop ends when b is 0, so return b always returns 0.
Repeated subtraction. The answer is right, but gcd(10**9, 1) takes about 10^9 steps. Use %.
The gcd of all values in nums. Find Greatest Common Divisor of Array (LC 1979) uses only the minimum and the maximum. For [2, 5, 6, 9, 10], the answer is 2, but the gcd of all five values is 1.
Wrong base case for a running gcd. Start from 0, not 1. gcd(0, x) is x, while gcd(1, x) is always 1.

Practice

Theory Context•Math & Geometry

P2EasyMental model~2 min speedrun

Euclidean Algorithm (Greatest Common Divisor)

Find Greatest Common Divisor of Array (LC 1979)(opens leetcode.com)

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.

Example 1

Input:nums = [2,5,6,9,10]

Output:2

The smallest value is 2 and the largest is 10. 2 divides 10, so their greatest common divisor is 2. (The five values together only share 1: just the two ends count.)

Euclid's GCD

two numbers ➔ replace (a, b) by (b, a % b) ➔ greatest common divisor

Euclid's GCD

Python

1	def gcd(a: int, b: int) -> int:
2	"""Euclid's algorithm: gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a."""
3	# 1. Replace the Pair Until It Shrinks to Zero (the trap):
4	# a % b is a minus a multiple of b, so a number dividing both a and b also divides a % b, and a
5	# number dividing b and a % b also divides a: both values must update from the old pair at once.
6	while b:
7	a, b = b, a % b
8	# 2. Return the Answer:
9	# The loop stops once b is 0; since gcd(a, 0) == a, a now holds the greatest common divisor.
10	return a
11
12
13	def find_gcd(nums: list[int]) -> int:
14	"""Find Greatest Common Divisor of Array: Euclid's algorithm on the smallest and largest value.
15	Time: O(N + log M) \| Space: O(1)
16	"""
17	lo, hi = min(nums), max(nums) # lo, hi: the two ends; only they matter, the other values play no part
18	return gcd(hi, lo)

Invariant: gcd(a, b) never changes from one loop step to the next, and b shrinks every step; when b is 0, a is the greatest common divisor.

See it run

Euclid's GCD, step by step

a 8b 3

Each row is one pair (a, b) the loop sees, and the remainder a % b that makes the next row.

read the starting pair (a, b)
remainder the value of a % b for this pair
new pair the pair after a, b = b, a % b
answer a when b is 0: the greatest common divisor

lo, hi = 3, 8. find_gcd returns gcd(8, 3), so the loop starts with a = 8 and b = 3.

pair 0

8read

3read

pair 1

pair 2

pair 3

1 / 9

Gotchas1 of 4

The trap
Gotcha 1: Writing a = b and then b = a % b
Mistake
```
a = b
b = a % b
```
Fix
```
a, b = b, a % b
```
What happens: After a = b, the old a is gone. The next line computes b % b, which is always 0. The loop stops after one step and returns the old b. So gcd(8, 3) returns 3 instead of 1.
Example: a = 8, b = 3
Mistake: returns 3Fix: returns 1
Gotcha 2: Returning b instead of a after the loop
Mistake
```
return b
```
Fix
```
return a
```
What happens: The loop stops when b is 0, so the pair ends as (g, 0). return b then always returns 0. The rule gcd(x, 0) == x also lets a running gcd start from 0, as in Number of Subarrays With GCD Equal to K (LC 2447).
Example: a = 8, b = 3
Mistake: returns 0Fix: returns 1
Gotcha 3: Using repeated subtraction instead of %
Mistake
```
while b:
    if a >= b:
        a -= b
    else:
        a, b = b, a
```
Fix
```
while b:
    a, b = b, a % b
```
What happens: Subtraction gives the same answer, but it can take a / b steps. For gcd(10**9, 1), that is about 10^9 steps. With %, the number of steps is at most about 2 * log2 of the smaller value.
Gotcha 4: Taking the gcd of all values in nums
Mistake
```
return functools.reduce(gcd, nums)
```
Fix
```
lo, hi = min(nums), max(nums)
return gcd(hi, lo)
```
What happens: Find Greatest Common Divisor of Array (LC 1979) asks for the gcd of only the smallest and the largest value. For [2, 5, 6, 9, 10], that is the gcd of 10 and 2, which is 2. The gcd of all five values is 1. Other problems do take the gcd of every value, such as X of a Kind in a Deck of Cards (LC 914) with its counts.
Example: nums = [2, 5, 6, 9, 10]
Mistake: returns 1Fix: returns 2

Not this one if…

Switch to Canonical Key when the gcd only puts each item into a standard form and the question is how many items share that form, as in Max Points on a Line (LC 149). See Canonical Key

Deep Dive

Why gcd(a, b) equals gcd(b, a % b)

The greatest common divisor (gcd) of two numbers is the largest number that divides both. Euclid's rule says gcd(a, b) == gcd(b, a % b).

So the pair (a, b) and the pair (b, r) have exactly the same common divisors. The largest one is the same, which means the gcd does not change.

The base case is gcd(a, 0) == a, because every number divides 0 and a is the largest divisor of a.

Why the loop ends fast

The remainder a % b is always smaller than b. So b shrinks every step, and it can only reach 0.

Repeated subtraction gives the same answer, but gcd(10**9, 1) would take about 10^9 steps. The % operator removes many subtractions at once.

Trace for find_gcd([7, 5, 6, 8, 3]): the answer is 1

The other examples of Find Greatest Common Divisor of Array (LC 1979) also work. For [2, 5, 6, 9, 10], the pair is (10, 2), 10 % 2 = 0, and the answer is 2. For [3, 3], the answer is 3.

Cost and where the gcd shows up

gcd takes O(log M) time and O(1) space, where M is the smaller input. find_gcd also scans the array once for min and max, so it takes O(N + log M) time in total.

When the gcd only turns each item into a standard form, as in Max Points on a Line (LC 149), the question is how many items share the form. That is the Canonical Key card.

60-Second Pitch

Common Questions

Why is gcd(a, b) equal to gcd(b, a % b)?: Write a = q * b + r. A number that divides a and b divides a - q * b, which is r. A number that divides b and r divides q * b + r, which is a. So both pairs have the same common divisors, and the largest one is the same.
What is the time complexity?: O(log M), where M is the smaller input. The larger value at least halves every two steps. The worst case is two consecutive Fibonacci numbers: gcd(832040, 514229) takes 28 steps.
Why write a, b = b, a % b as one statement?: Python computes the right side from the old a and b before it assigns either name. Two separate lines, a = b and then b = a % b, compute b % b = 0 on the second line. The loop then ends after one step with the wrong value.
How do you find the gcd of a whole array?: Fold it: g = 0, then g = gcd(g, x) for each x. This works because gcd(0, x) == x. Note that Find Greatest Common Divisor of Array (LC 1979) is different: it asks for the gcd of the smallest and the largest value only.
How do you get the least common multiple (LCM)?: Use lcm(a, b) = a // gcd(a, b) * b. Divide first to keep the intermediate value small. For a = 4 and b = 6, the gcd is 2 and the lcm is 12.

SWE Reasoning

Spot it

The problem asks for the largest number that divides several numbers (Find Greatest Common Divisor of Array (LC 1979)).
Two things must be cut into pieces of the same length, or share a period (Greatest Common Divisor of Strings (LC 1071)).
Items must form groups of one equal size, or all values must be reachable by integer steps (X of a Kind in a Deck of Cards (LC 914), Check If It Is a Good Array (LC 1250)).
A fraction or a direction must be reduced to lowest terms (Max Points on a Line (LC 149)).

The invariant, step by step

The pair is (a, b). Its gcd is some number g.
a % b equals a minus a multiple of b. So the common divisors of (a, b) are exactly the common divisors of (b, a % b).
a, b = b, a % b replaces the pair, and the gcd stays g.
a % b < b, so b gets smaller every step.
b cannot go below 0, so it reaches 0. At that point the pair is (g, 0).
gcd(g, 0) == g, so the loop returns a.

Traps

a = b then b = a % b. The second line computes b % b = 0. gcd(8, 3) returns 3 instead of 1.
return b after the loop. The loop ends when b is 0, so return b always returns 0.
Repeated subtraction. The answer is right, but gcd(10**9, 1) takes about 10^9 steps. Use %.
The gcd of all values in nums. Find Greatest Common Divisor of Array (LC 1979) uses only the minimum and the maximum. For [2, 5, 6, 9, 10], the answer is 2, but the gcd of all five values is 1.
Wrong base case for a running gcd. Start from 0, not 1. gcd(0, x) is x, while gcd(1, x) is always 1.

Practice

Theory Context•Math & Geometry

P2EasyMental model~2 min speedrun

Euclidean Algorithm (Greatest Common Divisor)

Find Greatest Common Divisor of Array (LC 1979)(opens leetcode.com)

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.

Example 1

Input:nums = [2,5,6,9,10]

Output:2

The smallest value is 2 and the largest is 10. 2 divides 10, so their greatest common divisor is 2. (The five values together only share 1: just the two ends count.)

Euclid's GCD

two numbers ➔ replace (a, b) by (b, a % b) ➔ greatest common divisor

Euclid's GCD

Python

1	def gcd(a: int, b: int) -> int:
2	"""Euclid's algorithm: gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a."""
3	# 1. Replace the Pair Until It Shrinks to Zero (the trap):
4	# a % b is a minus a multiple of b, so a number dividing both a and b also divides a % b, and a
5	# number dividing b and a % b also divides a: both values must update from the old pair at once.
6	while b:
7	a, b = b, a % b
8	# 2. Return the Answer:
9	# The loop stops once b is 0; since gcd(a, 0) == a, a now holds the greatest common divisor.
10	return a
11
12
13	def find_gcd(nums: list[int]) -> int:
14	"""Find Greatest Common Divisor of Array: Euclid's algorithm on the smallest and largest value.
15	Time: O(N + log M) \| Space: O(1)
16	"""
17	lo, hi = min(nums), max(nums) # lo, hi: the two ends; only they matter, the other values play no part
18	return gcd(hi, lo)

Invariant: gcd(a, b) never changes from one loop step to the next, and b shrinks every step; when b is 0, a is the greatest common divisor.

See it run

Euclid's GCD, step by step

a 8b 3

Each row is one pair (a, b) the loop sees, and the remainder a % b that makes the next row.

read the starting pair (a, b)
remainder the value of a % b for this pair
new pair the pair after a, b = b, a % b
answer a when b is 0: the greatest common divisor

lo, hi = 3, 8. find_gcd returns gcd(8, 3), so the loop starts with a = 8 and b = 3.

pair 0

8read

3read

pair 1

pair 2

pair 3

1 / 9

Gotchas1 of 4

The trap
Gotcha 1: Writing a = b and then b = a % b
Mistake
```
a = b
b = a % b
```
Fix
```
a, b = b, a % b
```
What happens: After a = b, the old a is gone. The next line computes b % b, which is always 0. The loop stops after one step and returns the old b. So gcd(8, 3) returns 3 instead of 1.
Example: a = 8, b = 3
Mistake: returns 3Fix: returns 1
Gotcha 2: Returning b instead of a after the loop
Mistake
```
return b
```
Fix
```
return a
```
What happens: The loop stops when b is 0, so the pair ends as (g, 0). return b then always returns 0. The rule gcd(x, 0) == x also lets a running gcd start from 0, as in Number of Subarrays With GCD Equal to K (LC 2447).
Example: a = 8, b = 3
Mistake: returns 0Fix: returns 1
Gotcha 3: Using repeated subtraction instead of %
Mistake
```
while b:
    if a >= b:
        a -= b
    else:
        a, b = b, a
```
Fix
```
while b:
    a, b = b, a % b
```
What happens: Subtraction gives the same answer, but it can take a / b steps. For gcd(10**9, 1), that is about 10^9 steps. With %, the number of steps is at most about 2 * log2 of the smaller value.
Gotcha 4: Taking the gcd of all values in nums
Mistake
```
return functools.reduce(gcd, nums)
```
Fix
```
lo, hi = min(nums), max(nums)
return gcd(hi, lo)
```
What happens: Find Greatest Common Divisor of Array (LC 1979) asks for the gcd of only the smallest and the largest value. For [2, 5, 6, 9, 10], that is the gcd of 10 and 2, which is 2. The gcd of all five values is 1. Other problems do take the gcd of every value, such as X of a Kind in a Deck of Cards (LC 914) with its counts.
Example: nums = [2, 5, 6, 9, 10]
Mistake: returns 1Fix: returns 2

Not this one if…

Switch to Canonical Key when the gcd only puts each item into a standard form and the question is how many items share that form, as in Max Points on a Line (LC 149). See Canonical Key

Deep Dive

Why gcd(a, b) equals gcd(b, a % b)

The greatest common divisor (gcd) of two numbers is the largest number that divides both. Euclid's rule says gcd(a, b) == gcd(b, a % b).

So the pair (a, b) and the pair (b, r) have exactly the same common divisors. The largest one is the same, which means the gcd does not change.

The base case is gcd(a, 0) == a, because every number divides 0 and a is the largest divisor of a.

Why the loop ends fast

The remainder a % b is always smaller than b. So b shrinks every step, and it can only reach 0.

Repeated subtraction gives the same answer, but gcd(10**9, 1) would take about 10^9 steps. The % operator removes many subtractions at once.

Trace for find_gcd([7, 5, 6, 8, 3]): the answer is 1

The other examples of Find Greatest Common Divisor of Array (LC 1979) also work. For [2, 5, 6, 9, 10], the pair is (10, 2), 10 % 2 = 0, and the answer is 2. For [3, 3], the answer is 3.

Cost and where the gcd shows up

gcd takes O(log M) time and O(1) space, where M is the smaller input. find_gcd also scans the array once for min and max, so it takes O(N + log M) time in total.

When the gcd only turns each item into a standard form, as in Max Points on a Line (LC 149), the question is how many items share the form. That is the Canonical Key card.

60-Second Pitch

Common Questions

Why is gcd(a, b) equal to gcd(b, a % b)?: Write a = q * b + r. A number that divides a and b divides a - q * b, which is r. A number that divides b and r divides q * b + r, which is a. So both pairs have the same common divisors, and the largest one is the same.
What is the time complexity?: O(log M), where M is the smaller input. The larger value at least halves every two steps. The worst case is two consecutive Fibonacci numbers: gcd(832040, 514229) takes 28 steps.
Why write a, b = b, a % b as one statement?: Python computes the right side from the old a and b before it assigns either name. Two separate lines, a = b and then b = a % b, compute b % b = 0 on the second line. The loop then ends after one step with the wrong value.
How do you find the gcd of a whole array?: Fold it: g = 0, then g = gcd(g, x) for each x. This works because gcd(0, x) == x. Note that Find Greatest Common Divisor of Array (LC 1979) is different: it asks for the gcd of the smallest and the largest value only.
How do you get the least common multiple (LCM)?: Use lcm(a, b) = a // gcd(a, b) * b. Divide first to keep the intermediate value small. For a = 4 and b = 6, the gcd is 2 and the lcm is 12.

SWE Reasoning

Spot it

The problem asks for the largest number that divides several numbers (Find Greatest Common Divisor of Array (LC 1979)).
Two things must be cut into pieces of the same length, or share a period (Greatest Common Divisor of Strings (LC 1071)).
Items must form groups of one equal size, or all values must be reachable by integer steps (X of a Kind in a Deck of Cards (LC 914), Check If It Is a Good Array (LC 1250)).
A fraction or a direction must be reduced to lowest terms (Max Points on a Line (LC 149)).

The invariant, step by step

The pair is (a, b). Its gcd is some number g.
a % b equals a minus a multiple of b. So the common divisors of (a, b) are exactly the common divisors of (b, a % b).
a, b = b, a % b replaces the pair, and the gcd stays g.
a % b < b, so b gets smaller every step.
b cannot go below 0, so it reaches 0. At that point the pair is (g, 0).
gcd(g, 0) == g, so the loop returns a.

Traps

a = b then b = a % b. The second line computes b % b = 0. gcd(8, 3) returns 3 instead of 1.
return b after the loop. The loop ends when b is 0, so return b always returns 0.
Repeated subtraction. The answer is right, but gcd(10**9, 1) takes about 10^9 steps. Use %.
The gcd of all values in nums. Find Greatest Common Divisor of Array (LC 1979) uses only the minimum and the maximum. For [2, 5, 6, 9, 10], the answer is 2, but the gcd of all five values is 1.
Wrong base case for a running gcd. Start from 0, not 1. gcd(0, x) is x, while gcd(1, x) is always 1.