Basic Mathematics for Data Structures & Algorithms (DSA) | Euclidean Algorithm

Welcome to the comprehensive study notes for Basic Mathematics for DSA, part of Striver’s A2Z DSA Course. This module establishes the crucial mathematical foundations required before tackling advanced algorithmic and data structure problems. Mastering these core concepts ensures robust problem-solving intuition and optimized code design.

1. Why Do We Need Basic Mathematics in DSA?

When starting out in Data Structures and Algorithms, diving straight into complex graph algorithms or dynamic programming can overwhelm your cognitive faculties.

Note: Building a solid foundation in basic mathematics trains your brain to recognize patterns in numbers, understand logarithmic time complexities, and manipulate integer representations efficiently.

By mastering fundamental operations like digit extraction, factor discovery, and greatest common divisor calculations early on, you build the mental scaffolding needed for advanced optimization.

2. Core Mental Model: The Digit Extraction Pattern

The absolute cornerstone of basic math problems in DSA is the Digit Extraction Pattern. If you know how to isolate and manipulate individual digits of an integer, you can solve dozens of introductory problems effortlessly.

Real-Life Analogy: Unstacking a Box of Numbered Blocks

Imagine you have a vertical stack of wooden blocks with digits written on them: [7][7][8][9] (representing the number $7789$). If you want to read or process every block individually from bottom to top (or right to left), how do you do it? You can only easily pull off the topmost (rightmost) block at any given moment. Once you pull off 9, you are left with 778, and you repeat the process until no blocks remain.

Code Implementation: Extracting and Printing Digits

Here is how the digit extraction loop is implemented in C++:

int n = 7789;
while (n > 0) {
    int lastDigit = n % 10;
    cout << lastDigit << " ";
    n = n / 10; // Integer division
}
// Output printed: 9 8 7 7

3. Problem 1: Count Digits

Problem Statement

Given an integer n, find and return the total number of digits present in n.

• Example: n = 156 $\rightarrow$ Output: 3 digits.
• Example: n = 7 $\rightarrow$ Output: 1 digit.

Solution Evolution

1. Iterative Extraction Approach: Wrap a counter variable inside the digit extraction loop. Every time a digit is extracted, increment count++. The loop runs exactly as many times as there are digits.
2. Logarithmic Approach: Mathematically, the number of digits in base 10 for a number n is given by $\lfloor \log_{10}(n) \rfloor + 1$.

// Logarithmic Approach in C++
#include <iostream>
#include <cmath>
using>

int countDigits(int n) {
    int count = (int)(log10(n) + 1);
    return count;
}

4. Problem 2: Reverse a Number

Problem Statement

Write a program to generate the reverse of a given number.

• Note: If a number has trailing zeros, its reverse will omit them (e.g., reverse of 10400 is 401, not 00401).
• Example: 7789 $\rightarrow$ 9877.

Mathematical Trick for Reversing

To build a reversed number dynamically, at each step we shift our accumulated reverse number one decimal place to the left (multiply by 10) and add the newly extracted digit:

Complete Code Walkthrough

int reverseNumber(int n) {
    int revNum = 0;
    while (n > 0) {
        int lastDigit = n % 10;
        revNum = (revNum * 10) + lastDigit;
        n = n / 10;
    }
    return revNum;
}

5. Problem 3: Check Palindrome

Problem Statement

Determine if a given number is a palindrome. A palindrome number reads the same forwards and backwards (e.g., 121, 1331, 11).

The Duplicate Variable Trap

Crucial Bug Warning: During digit extraction, n is completely reduced to 0. If you compare n directly with your computed revNum at the end of the loop, n will always be 0.

Solution: Always store an immutable copy (duplicate) of n before running the extraction loop.

bool isPalindrome(int n) {
    int dup = n;
    int revNum = 0;
    while (n > 0) {
        int lastDigit = n % 10;
        revNum = (revNum * 10) + lastDigit;
        n = n / 10;
    }
    return (dup == revNum);
}

6. Problem 4: Armstrong Numbers

Problem Statement

An Armstrong number is a number that is equal to the sum of the cubes (or the power of the number of digits) of its own digits.

• Example: 371 $\rightarrow$ $3^3 + 7^3 + 1^3 = 27 + 343 + 1 = 371$ (True).

Code Implementation

bool isArmstrong(int n) {
    int dup = n;
    int sum = 0;
    while (n > 0) {
        int lastDigit = n % 10;
        sum = sum + (lastDigit * lastDigit * lastDigit);
        n = n / 10;
    }
    return (dup == sum);
}

7. Problem 5: Print All Divisors

Problem Statement

Given a number n, print all its divisors (factors) in sorted order.

• Example: n = 36 $\rightarrow$ Divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Naive vs. Optimized Square Root Approach

Mathematical Observation for Pairs

If i is a factor of n (n % i == 0), then its corresponding paired factor is n / i.

• For n = 36, when i = 2, the paired factor is 36 / 2 = 18.

Optimized Code Implementation (Using C++ Vectors)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printDivisors(int n) {
    vector<int> ls;
    
    // Loop up to sqrt(n) implemented as i * i <= n to avoid floating-point overhead
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ls.push_back(i);
            // Push the counterpart factor if it is distinct
            if ((n / i) != i) {
                ls.push_back(n / i);
            }
        }
    }
    
    // Sort factors to print in proper ascending order
    sort(ls.begin(), ls.end());
    
    for (int it : ls) {
        cout << it << " ";
    }
}

8. Problem 6: Check for Prime Number

Problem Statement

Determine if a number is prime.

• Incorrect Definition: A number divisible only by 1 and itself (this incorrectly classifies 1 as a prime).
• Correct Definition: A number that has exactly two distinct factors: 1 and itself.

Optimized Prime Checking ($\sqrt{n}$ Algorithm)

Instead of checking all numbers up to n ($O(n)$ time complexity), we only iterate up to $\sqrt{n}$ and count factors. If the total factor count equals 2, it is prime.

bool isPrime(int n) {
    int cnt = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cnt++;
            // If factors are distinct, count both
            if ((n / i) != i) {
                cnt++;
            }
        }
    }
    return (cnt == 2);
}

9. Greatest Common Divisor (GCD) or Highest Common Factor (HCF)

Problem Statement

Given two integers N1 and N2, find the greatest integer that divides both of them without leaving a remainder.

• Example: GCD of 9 and 12 is 3.
• Example: GCD of 20 and 40 is 20.

The Naive Subtraction / Iteration Approach

You could loop downwards from $\min(N1, N2)$ to 1 and check the first number that divides both inputs. In the worst case (e.g., coprime numbers like 11 and 13), this takes $O(\min(N1, N2))$ time.

10. The Euclidean Algorithm for GCD

Core Mathematical Principle

The Euclidean algorithm states that the GCD of two numbers A and B (where A > B) is the same as the GCD of A - B and B.

Optimization via Modulo Operator

Repeatedly subtracting a smaller number from a larger number is essentially division. Instead of successive subtractions, we can jump straight to the remainder using the modulo operator:

Complete Flow Walkthrough (A = 52, B = 10)

Clean Code Implementation

int findGCD(int a, int b) {
    while (a > 0 && b > 0) {
        if (a > b) {
            a = a % b;
        } else {
            b = b % a;
        }
    }
    if (a == 0) return b;
    return a;
}

Time Complexity Analysis

• Time Complexity: $O(\log_{\phi}(\min(A, B)))$, where $\phi$ represents the golden ratio. Because the algorithm uses division/modulo operations to reduce numbers logarithmically, it executes extremely fast even for massive numbers.

11. Summary and Key Takeaways

• Digit Extraction Foundation: Isolating digits using % 10 and shrinking numbers using / 10 is the bedrock for solving numerical DSA problems.
• Avoid Mutability Bugs: Always store a duplicate copy (dup = n) if you need the original number later, as extraction loops reduce n to 0.
• Square Root Optimization: Factor-related problems (printDivisors, isPrime) should always be bounded by $\sqrt{n}$ ($i * i \le n$) rather than linear $O(n)$ to ensure optimal performance.
• Factor Pairing: Every factor i has a counterpart factor n / i.
• Prime Definition Precision: A prime number is strictly defined as a number having exactly two distinct factors (1 and itself).
• Euclidean Algorithm: GCD calculations are optimized from linear time down to logarithmic time ($O(\log \min(A, B))$) by repeatedly applying modulo operations (a % b or b % a) until one operand becomes 0.