Skip to content

Volume ITechnology

4.0.6 — HCF and LCM ​

Classic · Easy · LeetCode 1979 (Find GCD of Array), LeetCode 1071 (GCD of Strings)

The problem ​

Given two whole numbers, find:

  • their HCF, the highest common factor. This is the largest number that divides both exactly. It is also called the GCD, the greatest common divisor. Same thing, two names. HCF of 12 and 18 is 6.
  • their LCM, the least common multiple. This is the smallest number that both divide exactly. LCM of 12 and 18 is 36.

Then do the same for a whole list of numbers.

Where you meet these ​

HCF simplifies fractions. \frac{12}{18}: divide top and bottom by their HCF, 6, and you get \frac{2}{3}.

LCM answers "when do two repeating things line up again?" One bus comes every 12 minutes and another every 18 minutes. Both leave the station now. They next leave together after 36 minutes, the LCM. It is also the common denominator you use to add \frac{1}{12} + \frac{1}{18}.

The school method, and why programs avoid it ​

At school you factorise both numbers into primes, using the loop from 4.0.5.

12 = 2^2 \times 3 \qquad 18 = 2 \times 3^2

The HCF takes each prime with its smaller power: 2^1 \times 3^1 = 6. The LCM takes each prime with its larger power: 2^2 \times 3^2 = 36.

This is correct, and it explains what HCF and LCM really are. But factorising costs O(\sqrt{n}) steps per number. For numbers near 10^{18} that is a billion steps. Euclid found a far faster way.

Euclid's idea, first with subtraction ​

Any number that divides both a and b also divides a - b.

Why? Say d divides both. Then a = d \times x and b = d \times y for some whole numbers x and y. So a - b = d \times (x - y), which is also a multiple of d.

It works the other way too. Anything that divides both b and a - b also divides their sum, which is a. So the pair (a, b) and the pair (a - b, b) have exactly the same common divisors. That means they have the same HCF. But the second pair is smaller.

So keep replacing the larger number with the difference. When the two become equal, that value is the HCF.

python
def hcf_subtract(a: int, b: int) -> int:
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

print(hcf_subtract(12, 18))   # → 6

The pairs go (12, 18) \to (12, 6) \to (6, 6). The answer is 6.

The problem with subtraction. For hcf_subtract(1_000_000, 1) it subtracts 1 nearly a million times. All those subtractions of the same number are really one division. The remainder after dividing is exactly what you get after subtracting as many times as fits.

Euclid's algorithm with remainders ​

Replace "subtract b again and again" with "take the remainder after dividing by b".

\gcd(a, b) = \gcd(b,\ a \bmod b)

Read it aloud: "the HCF of a and b equals the HCF of b and the remainder of a divided by b." When the second number reaches 0, the first number is the answer. Why does 0 end it? Every number divides 0, since 0 = d \times 0. So the HCF of x and 0 is just x.

python
def hcf(a: int, b: int) -> int:
    while b != 0:          # (1)
        a, b = b, a % b    # (2)
    return a               # (3)

print(hcf(12, 18))         # → 6
print(hcf(1071, 462))      # → 21
print(hcf(17, 5))          # → 1

(1) Keep going until the remainder is 0.

(2) The new pair is (old b, remainder). This uses the tuple swap from 4.0.1. Both new values are computed from the old pair before either is stored.

(3) When b is 0, a holds the HCF.

You do not need a >= b to start. If a is smaller, the first step gives a % b = a, and the pair simply swaps. For hcf(12, 18): (12, 18) \to (18, 12) \to (12, 6) \to (6, 0). The answer is 6.

Trace on 1071 and 462:

aba % b
1071462147
46214721
147210
210stop

The HCF is 21. Check: 1071 = 21 \times 51 and 462 = 21 \times 22.

How fast is it? Every two steps, the larger number at least halves. Here is why. Take a \bmod b. If b is at most half of a, the remainder is smaller than b, so it is below half of a. If b is more than half of a, then b fits once and the remainder is a - b, which is again below half of a. Halving every two steps means about 2 \log_2 n steps at most. For numbers near 10^{18}, that is under 130 steps.

Learn two HCF facts by heart. Two numbers with HCF 1 are called coprime. 17 and 5 are coprime. And the slowest inputs for Euclid are neighbouring Fibonacci numbers, like 89 and 55, because each remainder is the Fibonacci number just below.

The recursive version is the same rule written as a function that calls itself.

python
def hcf_rec(a: int, b: int) -> int:
    return a if b == 0 else hcf_rec(b, a % b)

print(hcf_rec(48, 180))   # → 12

LCM from the HCF ​

Here is the link between the two. For any two positive numbers:

a \times b = \text{HCF}(a, b) \times \text{LCM}(a, b)

Why? Look at the prime powers again. For each prime, the HCF takes the smaller power and the LCM takes the larger. Smaller plus larger always equals the two powers added together, which is exactly what a \times b has. For 12 and 18 and the prime 2: the powers are 2 and 1. HCF takes 1, LCM takes 2, and 1 + 2 = 3, which is the power of 2 in 12 \times 18 = 216 = 2^3 \times 3^3.

So the LCM is the product divided by the HCF.

python
def lcm(a: int, b: int) -> int:
    return a // hcf(a, b) * b      # (1)

print(lcm(12, 18))    # → 36
print(lcm(4, 6))      # → 12

(1) Divide before multiplying. a * b // hcf(a, b) gives the same answer, but a * b can be huge. In Python that only costs time. In Java or C it overflows and gives a wrong answer. Dividing first keeps every middle value no bigger than the answer.

HCF and LCM of a whole list ​

The HCF of three numbers is the HCF of the first two, then combined with the third. The same holds for the LCM. So fold the list one number at a time.

python
from functools import reduce

def hcf_list(nums: list[int]) -> int:
    return reduce(hcf, nums)

def lcm_list(nums: list[int]) -> int:
    return reduce(lcm, nums)

print(hcf_list([24, 36, 60]))     # → 12
print(lcm_list([2, 3, 4, 5]))     # → 60

reduce(hcf, [24, 36, 60]) computes hcf(hcf(24, 36), 60), which is hcf(12, 60), which is 12.

A shortcut for the HCF. Once the running HCF reaches 1, it can never go higher. You can stop early.

In real Python code, use math.gcd(a, b) and math.lcm(a, b). From Python 3.9 both accept any number of arguments: math.gcd(24, 36, 60) gives 12.

Edge cases ​

  • Zero. \gcd(a, 0) = a, since every number divides 0. \text{lcm}(a, 0) is defined as 0. Our lcm would compute 0 // hcf(0, b) * b. hcf(0, b) is b, so that is 0 // b * b = 0. Correct. But lcm(0, 0) divides by zero. Guard it if zeros are possible.
  • Negative numbers. HCF is usually defined as positive. Pass abs(a) and abs(b).

Complexity ​

HCF: O(\log \min(a, b)) time, O(1) memory. LCM: the same, plus one division and one multiplication. For a list of n numbers: O(n \log M), where M is the largest value.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Why does Euclid's method work?" Any number that divides both a and b also divides the remainder of a divided by b. So the pair (a, b) and the pair (b, a \bmod b) have the same common divisors. The second pair is smaller, so you keep going until the remainder is 0.

"How fast is it?" Very fast. Every two steps, the bigger number is at least cut in half. So it takes about 2 \log_2 n steps. For numbers near 10^{18}, that is under 130 steps.

"How do you get the LCM?" Use HCF × LCM = a \times b. So LCM = a // hcf(a, b) * b. Divide first and multiply second, so the middle value never gets too big.

"How do you find the HCF of a whole list?" Find the HCF of the first two numbers. Then the HCF of that answer with the third number. Continue to the end. If the answer ever becomes 1, you can stop early.

"Find the GCD of two strings." This is LeetCode 1071. First check s1 + s2 == s2 + s1. If not, there is no answer. If yes, the answer is the first \gcd(\text{len}(s1), \text{len}(s2)) characters of s1.

One thing to volunteer: "Euclid's method is over 2,300 years old, and computers still use it today."

Next: 4.0.7 Factorial and Trailing Zeros. A simple product, then a question about how many zeros it ends with.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet