Day 7: 8 Mathematical Patterns Every Programmer Must Know for DSA

Unlock the key mathematical tricks and patterns that power algorithms, simplify complex problems, and help you ace coding interviews

Math is fundamental to every field of engineering. It helps us calculate, analyze, and arrive at accurate results. Any programmer who wants to excel must have a strong grasp of math, otherwise, they’re just performing CRUD operations or copying and pasting code without understanding it.

Similarly, DSA (Data Structures and Algorithms) is crucial for interviews because it tests your problem-solving skills and logical thinking. In this article, I’m going to explain the 8 most important math patterns that will help you solve DSA problems with confidence.

Note: Don’t just memorize these patterns, try to understand them deeply. Solve at least 5 problems on each pattern, and you’ll truly master them.

---

1. GCD & LCM (Euclidean Algorithm)

GCD (Greatest Common Divisor):
The GCD is basically the largest number that divides two numbers completely.

• Think of it as: "What is the biggest number they both share as a factor?"

Example:
Find GCD of 48 and 18:

• Factors of 48 = {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}

• Factors of 18 = {1, 2, 3, 6, 9, 18}

• Common factors = {1, 2, 3, 6}

• The greatest common factor = 6

GCD(48, 18) = 6

pseudocode for find GCD

function GCD(a, b):
    while b != 0:
        temp = b
        b = a mod b
        a = temp
    return a

Dry Run Time:

Function Call: GCD(48, 18)

Initial values:

a = 48, b = 18

Step 1: (while b != 0 → true since b = 18)

temp = b = 18
b = a mod b = 48 mod 18 = 12
a = temp = 18

Now: a = 18, b = 12

Step 2: (while b != 0 → true since b = 12)

temp = b = 12
b = a mod b = 18 mod 12 = 6
a = temp = 12

Now: a = 12, b = 6

Step 3: (while b != 0 → true since b = 6)

temp = b = 6
b = a mod b = 12 mod 6 = 0
a = temp = 6

Now: a = 6, b = 0

Step 4: (while b != 0 → false since b = 0)
Exit loop.

Return:

a = 6

GCD(48, 18) = 6

When to Use GCD

• Simplifying fractions → e.g., reduce 4818\frac{48}{18}1848​ to lowest terms.

• Checking co-prime numbers (two numbers are co-prime if GCD = 1).

• Tiling / partition problems → e.g., find the largest square tile that can exactly fill a floor of size 48 × 18.

• Cycle problems → finding repeating cycles in strings, arrays, or modular arithmetic.

• Cryptography / Number Theory → Extended Euclidean Algorithm is the base for Modular Inverse (used in RSA, etc.).

  ---

LCM (Least Common Multiple):
The LCM is the smallest number that is divisible by both numbers.

Think of it as: "What is the smallest number they both can reach if you keep multiplying them?"

Example:
For 4 and 6:

• Multiples of 4 → 4, 8, 12, 16…

• Multiples of 6 → 6, 12, 18…

• First common multiple → 12

So, LCM(4, 6) = 12

pseudocode for find LCM

function LCM(a, b):
    gcd = GCD(a, b)
    return (a * b) / gcd

There’s a beautiful math connection:

GCD(a, b) × LCM(a, b) = a × b #try it

When to Use LCM

You use LCM when you need to find a common repeating point or synchronize events.

• Scheduling problems → e.g., two buses arrive every 18 min and 48 min; when will they meet again? (answer: 144 min).

• Array problems → LCM of array elements is used in some math-heavy questions.

• Simulations → repeating signals, lights blinking, or circular problems where events overlap.

• Fraction addition → common denominator calculation uses LCM.

Leetcode Problem to practice

• Find Greatest Common Divisor of Array

• Number of Subarrays With LCM Equal to K

• Greatest Common Divisor of Strings

• GCD Sort of an Array

• Ugly Number III

---

Certainly! Here’s the revised section on Prime Numbers & Sieve of Eratosthenes with clickable hyperlinks to the relevant LeetCode problems:

---

2. Prime Numbers & Sieve of Eratosthenes

Prime Numbers:
A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Think of it as: “Can I only divide this number by 1 and itself without leaving a remainder?”

Example: Check if 29 is prime.

• Divisors of 29 = {1, 29} → Prime

• Divisors of 30 = {1, 2, 3, 5, 6, 10, 15, 30} → Not prime

Naive Approach (Check Divisibility)

Pseudocode:

function isPrime(n):
    if n <= 1:
        return False
    for i from 2 to sqrt(n):
        if n mod i == 0:
            return False
    return True

Dry Run Example: Check isPrime(29)

• i = 2 → 29 mod 2 ≠ 0

• i = 3 → 29 mod 3 ≠ 0

• i = 4 → 29 mod 4 ≠ 0

• i = 5 → 29 mod 5 ≠ 0 (sqrt(29) ≈ 5.38 → stop here)

• No divisor found → Prime

When to Use Naive Prime Check:

• Small numbers

• Ad-hoc checks in algorithms

Efficient Approach: Sieve of Eratosthenes

Used to generate all prime numbers up to N efficiently.

Idea:

• Start with a list of numbers from 2 to N.

• Repeatedly mark multiples of each prime as non-prime.

Pseudocode:

function Sieve(N):
    isPrime = [True] * (N+1)
    isPrime[0] = isPrime[1] = False

    for i from 2 to sqrt(N):
        if isPrime[i]:
            for j from i*i to N step i:
                isPrime[j] = False

    return all numbers i where isPrime[i] == True

Dry Run Example: Sieve(10)

• Start: [2,3,4,5,6,7,8,9,10] all True

• i = 2 → mark multiples 4, 6, 8, 10 → False

• i = 3 → mark multiples 9 → False

• Remaining True → [2,3,5,7]

Time Complexity: O(N log log N)
Space Complexity: O(N)

When to Use Prime Numbers & Sieve:

• Number theory problems → prime factorization, GCD/LCM optimizations

• Cryptography → RSA, modular arithmetic

• Counting problems → Euler’s totient, coprime counts

• Competitive programming → generate primes once, reuse for multiple queries

LeetCode / Practice Problems:

• Count Primes

• Count the Number of Prime Factors of a Number

• Super Ugly Number

• Prime Subsets / Prime Sum Problems

---

3. Modular Arithmetic

Definition:
Modular arithmetic is a system where numbers wrap around after reaching a certain value, called the modulus.

Think of it like a clock: after 12 hours, it wraps back to 1.

Example:

• 15 mod 7 = 1 → because 15 ÷ 7 = 2 remainder 1

• 25 mod 5 = 0 → divisible

Properties

1. (a + b) % m = (a % m + b % m) % m

2. (a - b) % m = (a % m - b % m + m) % m

3. (a * b) % m = (a % m * b % m) % m

4. Modular inverse exists if gcd(a, m) = 1

Example: (10 + 14) % 6 = (10%6 + 14%6)%6 = (4 + 2)%6 = 0 ✅

When to Use Modular Arithmetic

• Avoid integer overflow in large numbers

• Hashing and combinatorics

• Cryptography (RSA, Diffie-Hellman)

• Problems with cyclic arrays or repeating patterns

LeetCode Practice:

• Pow(x, n)

• Subarray Sums Divisible by K

• Number of Good Subsets

---

4. Fast Exponentiation (Binary Exponentiation)

Definition:
Instead of multiplying a by itself b times to calculate a^b (O(b)), binary exponentiation computes it in O(log b) using divide-and-conquer.

Think of it as breaking the exponent into powers of 2.

Pseudocode

function power(a, b):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result *= a
        a *= a
        b //= 2
    return result

Dry Run Example: power(3, 5)

• b = 5 (odd) → result = 13 = 3, a = 33 = 9, b = 2

• b = 2 (even) → result = 3, a = 9*9 = 81, b = 1

• b = 1 (odd) → result = 3*81 = 243

When to Use

• Modular exponentiation in competitive programming

• Fibonacci via matrix exponentiation

• Large number computations

LeetCode Practice:

• Pow(x, n)

• Super Pow

---

5. Combinatorics & Pascal’s Triangle

Definition:
Combinatorics helps us count ways to arrange or select items.

• Factorial: n! = n*(n-1)*(n-2)*...*1

• Combination: nCr = n! / (r! * (n-r)!)

Think of it as: “In how many ways can I pick or arrange items?”

Pseudocode (nCr)

function nCr(n, r):
    return factorial(n) / (factorial(r) * factorial(n-r))

Dry Run Example: 5C2 = 5! / (2!*3!) = 10

Pascal’s Triangle

A triangular array of binomial coefficients:

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

• Each number = sum of the two numbers above it

• Can compute nCr efficiently

When to Use

• Probability problems

• Counting arrangements & selections

• Dynamic programming on combinatorial states

LeetCode Practice:

• Unique Paths

• Combinations

• Pascal’s Triangle

---

6. Fibonacci Numbers & Recurrence Relations

Definition:
A sequence where each number is the sum of the previous two.

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

Think of it as a pattern in nature and sequences.

Pseudocode (Iterative)

function fibonacci(n):
    a, b = 0, 1
    for i = 2 to n:
        c = a + b
        a = b
        b = c
    return b

Dry Run Example: F(5) → 0,1,1,2,3,5

When to Use

• Dynamic programming problems

• Recurrence relations

• Matrix exponentiation for fast calculation

LeetCode Practice:

• Climbing Stairs

• Nth Fibonacci Number

---

7. Number of Divisors & Sum of Divisors

Definition:
Count how many numbers divide a given number (divisors) or sum all divisors.

Example: 12 → divisors: {1,2,3,4,6,12} → count = 6, sum = 28

Pseudocode

function countDivisors(n):
    count = 0
    for i = 1 to sqrt(n):
        if n % i == 0:
            count += 2 if i != n/i else 1
    return count

Dry Run Example: n = 12

• i = 1 → 12%1 = 0 → count +=2 → count=2

• i = 2 → 12%2 =0 → count+=2 → count=4

• i = 3 → 12%3=0 → count+=2 → count=6

• i = 4 → 12%4=0 → already counted via i=2

Total divisors = 6

When to Use

• Factorization problems

• Tiling/floor problems

• Number theory optimizations

LeetCode Practice:

• Divisor Game

• Count Divisors of a Number

---

8. GCD/LCM of Multiple Numbers (Arrays)

Definition:
Extend GCD and LCM to arrays with multiple numbers.

• GCD of array = largest number that divides all numbers

• LCM of array = smallest number divisible by all numbers

Pseudocode (GCD of array)

function GCDArray(arr):
    result = arr[0]
    for i in 1 to n-1:
        result = GCD(result, arr[i])
    return result

Dry Run Example: arr = [48,18,30]

• GCD(48,18)=6

• GCD(6,30)=6

Use Cases:

• Synchronization problems (buses, events)

• Fraction simplification for multiple numbers

• Tiling and partitioning problems

LeetCode Practice:

• Find Greatest Common Divisor of Array

• Number of Subarrays With LCM Equal to K

---

Hope this article helps you.