Number Theory & Combinatorics in C: GCD, LCM, Primes, Sieve, Modular Arithmetic & Binomial Coefficients

1. What is GCD?

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. It’s used in fraction simplification, modular arithmetic, and more.

2. What is LCM?

The Least Common Multiple (LCM) of two integers is the smallest positive integer divisible by both. It’s used in problems like finding common periods or adding fractions.

3. How do you compute GCD?

Use the Euclidean Algorithm: GCD(a, b) = GCD(b, a % b) until b becomes 0. The last non-zero remainder is the GCD.

4. How do you compute LCM?

LCM(a, b) = (a * b) / GCD(a, b). To avoid overflow, compute as (a / GCD(a, b)) * b.

5. Can you give an example of GCD and LCM in C?

Example: Computing GCD and LCM for 12 and 18.

#include <stdio.h>

int gcd(int a, int b) {
    if (a < 0 || b < 0) return -1; // Handle negative numbers
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    if (a <= 0 || b <= 0) return -1; // Handle invalid inputs
    return (a / gcd(a, b)) * b; // Avoid overflow
}

int main() {
    int a = 12, b = 18;
    int gcd_result = gcd(a, b);
    if (gcd_result == -1) {
        printf("Invalid input\n");
        return 1;
    }
    printf("GCD(%d, %d) = %d\n", a, b, gcd_result); // Output: GCD(12, 18) = 6
    printf("LCM(%d, %d) = %d\n", a, b, lcm(a, b)); // Output: LCM(12, 18) = 36
    return 0;
}

6. What are the time and space complexities of GCD?

7. What are the applications of GCD and LCM?

8. What is a prime number?

A prime number is a natural number greater than 1 that is divisible only by 1 and itself (e.g., 2, 3, 5, 7).

9. How do you check if a number is prime?

Test divisibility from 2 to the square root of the number. If no divisors are found, the number is prime.

10. Can you give an example of a prime check in C?

Example: Checking if 17 and 15 are prime.

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
    if (n <= 1) return false; // Handle non-positive and 1
    if (n == 2) return true;
    if (n % 2 == 0) return false; // Check even numbers
    for (int i = 3; i <= sqrt(n); i += 2) { // Check odd divisors up to sqrt(n)
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    printf("Is 17 prime? %d\n", isPrime(17)); // Output: 1 (true)
    printf("Is 15 prime? %d\n", isPrime(15)); // Output: 0 (false)
    return 0;
}

11. What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given number n by iteratively marking multiples of each prime as non-prime.

12. Can you give an example of the Sieve of Eratosthenes in C?

Example: Finding all primes up to 20.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

void sieve(int n) {
    if (n < 2) {
        printf("No primes found\n");
        return;
    }
    bool* prime = (bool*)malloc((n + 1) * sizeof(bool));
    if (!prime) {
        printf("Memory allocation failed\n");
        return;
    }
    for (int i = 0; i <= n; i++) prime[i] = true;
    prime[0] = prime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i) { // Mark multiples as non-prime
                prime[j] = false;
            }
        }
    }
    
    printf("Primes up to %d: ", n);
    for (int i = 2; i <= n; i++) {
        if (prime[i]) printf("%d ", i);
    }
    printf("\n");
    free(prime); // Clean up memory
}

int main() {
    sieve(20); // Output: Primes up to 20: 2 3 5 7 11 13 17 19
    return 0;
}

13. What are the time and space complexities of the Sieve of Eratosthenes?

14. What are the applications of prime numbers and the Sieve?

15. What is Modular Arithmetic?

Modular arithmetic involves performing arithmetic operations (addition, subtraction, multiplication, exponentiation) where results are taken modulo a number (e.g., (a + b) % m). It’s used to handle large numbers efficiently.

16. What are the key properties of Modular Arithmetic?

17. What is Modular Exponentiation?

Modular Exponentiation computes (a^b) % m efficiently using the square-and-multiply algorithm, avoiding large intermediate results.

18. Can you give an example of Modular Exponentiation in C?

Example: Computing 2^10 % 1000000007.

#include <stdio.h>

long long modPow(long long base, long long exp, long long mod) {
    if (mod <= 0) return -1; // Handle invalid modulus
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod; // Multiply if bit is 1
        base = (base * base) % mod; // Square
        exp >>= 1; // Divide exponent by 2
    }
    return result;
}

int main() {
    long long base = 2, exp = 10, mod = 1000000007;
    printf("2^10 mod %lld = %lld\n", mod, modPow(base, exp, mod)); // Output: 1024
    return 0;
}

19. What are the time and space complexities of Modular Exponentiation?

20. What are the applications of Modular Arithmetic?

21. How do you compute the Modular Inverse?

The modular inverse of a (mod m) is a number x such that (a * x) % m = 1. Use the Extended Euclidean Algorithm.

#include <stdio.h>

int extendedGCD(int a, int b, int* x, int* y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = extendedGCD(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}

int modInverse(int a, int m) {
    if (a <= 0 || m <= 0) return -1; // Handle invalid inputs
    int x, y;
    int gcd = extendedGCD(a, m, &x, &y);
    if (gcd != 1) return -1; // Inverse doesn't exist
    return (x % m + m) % m; // Ensure positive result
}

int main() {
    int a = 3, m = 11;
    int result = modInverse(a, m);
    if (result == -1) {
        printf("Modular inverse does not exist\n");
    } else {
        printf("Modular inverse of %d mod %d = %d\n", a, m, result); // Output: 4
    }
    return 0;
}

22. What is Combinatorics in DSA?

Combinatorics deals with counting, arranging, and selecting objects, often used in algorithms for problems like permutations, combinations, and binomial coefficients.

23. What are key combinatorial concepts?

24. Can you give an example of computing Binomial Coefficients in C?

Example: Computing C(5, 2) modulo a prime to avoid overflow.

#include <stdio.h>

#define MOD 1000000007

long long binomialCoeff(int n, int r) {
    if (r < 0 || r > n) return 0; // Handle invalid inputs
    long long dp[r + 1];
    for (int i = 0; i <= r; i++) dp[i] = 0;
    dp[0] = 1; // Base case
    for (int i = 1; i <= n; i++) {
        for (int j = r; j > 0; j--) {
            dp[j] = (dp[j] + dp[j - 1]) % MOD; // C(i, j) = C(i-1, j) + C(i-1, j-1)
        }
    }
    return dp[r];
}

int main() {
    int n = 5, r = 2;
    printf("C(%d, %d) = %lld\n", n, r, binomialCoeff(n, r)); // Output: 10
    return 0;
}

25. What is the time complexity of computing Binomial Coefficients?

26. What is Probability in the context of DSA?

Probability in DSA involves calculating the likelihood of events, often used in randomized algorithms or expected value computations.

27. What are basic probability concepts?

28. Can you give an example of a probability-based problem?

Example: Expected number of coin flips to get heads: E[X] = 1 * (1/2) + 2 * (1/2)^2 + 3 * (1/2)^3 + ... = 2.

#include <stdio.h>

double expectedFlips() {
    return 2.0; // Analytical solution: E[X] = 1/(1/2) = 2
}

int main() {
    printf("Expected flips to get heads: %.2f\n", expectedFlips()); // Output: 2.00
    return 0;
}

29. What are the applications of Combinatorics and Probability in DSA?