Why Math and Number Theory Appear in DSA Problems in DSA C - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of GCD Calculation in a Loop

What is the output of the following C code that calculates the GCD of pairs of numbers?

DSA C

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int pairs[3][2] = {{12, 18}, {100, 80}, {7, 13}};
    for (int i = 0; i < 3; i++) {
        printf("%d\n", gcd(pairs[i][0], pairs[i][1]));
    }
    return 0;
}

A

6
20
1

B

6
10
0

C

6
20
0

D

6
10
1

💡 Hint

Recall the Euclidean algorithm for GCD and how modulo works.

The gcd function uses the Euclidean algorithm. gcd(12,18) = 6, gcd(100,80) = 20, gcd(7,13) = 1. The correct output matches option A.

🧠 Conceptual

intermediate

Why Use Number Theory in DSA?

Why do number theory concepts like prime numbers and modular arithmetic often appear in data structure and algorithm problems?

A Because they help optimize memory usage in data structures.

B Because they simplify sorting algorithms by reducing comparisons.

C Because they provide tools to solve problems involving divisibility, cycles, and hashing efficiently.

D Because they replace the need for recursion in algorithms.

💡 Hint

Think about common problem themes like hashing and cycles.

Number theory concepts like primes and modular arithmetic help solve problems involving divisibility, cycles, and hashing efficiently, which are common in DSA.

🔧 Debug

advanced

Find the Error in Modular Exponentiation Code

What error does the following C code produce when computing (base^exp) % mod?

DSA C

#include <stdio.h>

int mod_exp(int base, int exp, int mod) {
    int result = 1;
    for (int i = 0; i < exp; i++) {
        result = (result * base) % mod;
    }
    return result;
}

int main() {
    printf("%d\n", mod_exp(2, 10, 1000));
    return 0;
}

A No error, outputs 24 (correct output)

B No error, outputs 1024

C No error, outputs 24

D 42 stuptuo ,rorre oN

💡 Hint

Check the output of 2^10 mod 1000 carefully.

2^10 = 1024, 1024 % 1000 = 24, so output is 24. A correctly identifies no error and the correct output. Option A is wrong output.

❓ Predict Output

advanced

Output of Sieve of Eratosthenes Implementation

What is the output of the following C code that prints prime numbers up to 10?

DSA C

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

int main() {
    int n = 10;
    bool prime[11];
    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) {
                prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (prime[i]) printf("%d ", i);
    }
    return 0;
}

A 2 3 4 5 7

B 2 3 5 6 7

C 2 3 5 7 9

D 2 3 5 7

💡 Hint

Recall prime numbers up to 10.

The sieve marks non-primes false. Primes up to 10 are 2, 3, 5, 7. Options A, C, D include non-primes.

🚀 Application

expert

Number Theory in Cycle Detection in Graphs

How can number theory concepts help in detecting cycles in graphs using algorithms like Floyd's Tortoise and Hare?

A By sorting nodes based on their numeric values to find cycles.

B By applying modular arithmetic to detect repeated states efficiently.

C By using prime factorization to label nodes uniquely.

D By using GCD calculations to merge cycles.

💡 Hint

Think about how repeated states or positions are detected in cycle detection.

Floyd's algorithm uses two pointers moving at different speeds. Modular arithmetic helps detect repeated states efficiently by handling indices and positions in cycles.