Data Structures and Algorithms in C (DSA)

📘 Mathematics for DSA (GCD, LCM, Modulo Arithmetic)

Mathematics is the backbone of efficient algorithms in Data Structures. In this chapter, we cover essential concepts such as GCD, LCM, and Modulo Arithmetic that are frequently used in number theory, combinatorics, and optimization problems.

🧮 GCD (Greatest Common Divisor)

GCD of two numbers is the largest number that divides both numbers without leaving a remainder.

Example: GCD of 12 and 18 is 6.

🔁 Euclidean Algorithm

Efficient method to compute GCD:

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
  

🔗 LCM (Least Common Multiple)

LCM of two numbers is the smallest number divisible by both numbers.

Formula: LCM(a, b) = (a × b) / GCD(a, b)

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
  

➗ Modulo Arithmetic

Modulo (%) returns the remainder of a division. Used heavily in competitive programming to avoid overflow and in cyclic behavior problems (like clocks, circular arrays).

// Examples
7 % 3 = 1
10 % 5 = 0
-5 % 3 = -2 (in C)
  

⚠️ Modulo Tips

• (a + b) % m = ((a % m) + (b % m)) % m
• (a * b) % m = ((a % m) * (b % m)) % m
• (a - b + m) % m handles negative results

🧠 Modular Inverse (Advanced)

For solving equations like (a / b) % m, we use the Modular Inverse of b under m:

Use Fermat's Theorem when m is prime: b⁻¹ ≡ b^(m-2) mod m

// Fast Power to compute (base^exp) % mod
int power(int base, int exp, int mod) {
    int res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2) res = (1LL * res * base) % mod;
        base = (1LL * base * base) % mod;
        exp /= 2;
    }
    return res;
}
  

📚 Practice Problems

• Find GCD of 270 and 192
• LCM of 8 and 14
• Compute (123456 * 98765) % 1000000007
• Find modular inverse of 5 mod 13

✅ Summary

• Use GCD to simplify fractions, find common factors.
• LCM is used for scheduling and synchronization problems.
• Modulo is essential for safe arithmetic operations in large inputs.
• Modular inverse helps in division under modulo.

📤 Coming Next

In the next chapter, we’ll cover Arrays: Basics and Operations — the foundational structure for storing collections of data in DSA.