Why Math and Number Theory Appear in DSA Problems in DSA C - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the greatest common divisor (GCD) of two numbers using Euclid's algorithm.

DSA C

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

Drag options to blanks, or click blank then click option'

Atemp

Ba

Cb

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'a' instead of 'b' in the modulo operation.

Confusing variable names leading to wrong modulo calculation.

The Euclid's algorithm uses the remainder of a divided by b, so the blank should be 'b' to compute 'a % b'.

2fill in blank

medium

Complete the code to check if a number 'n' is prime by testing divisibility up to its square root.

DSA C

#include <math.h>

int is_prime(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i <= [1]; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

Drag options to blanks, or click blank then click option'

An / 2

Bsqrt(n)

Cn - 1

Dn / 3

Attempts:

3 left

💡 Hint

Common Mistakes

Checking divisibility up to n-1 which is inefficient.

Using n/2 which is more than needed.

To check primality efficiently, we only need to test divisors up to the square root of 'n'.

3fill in blank

hard

Fix the error in the code to compute the modular exponentiation (a^b mod m) efficiently.

DSA C

int mod_exp(int a, int b, int m) {
    int result = 1;
    a = a % m;
    while (b > 0) {
        if (b [1] 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b = b / 2;
    }
    return result;
}

Drag options to blanks, or click blank then click option'

A&

B|

C^

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using equality '==' instead of bitwise AND.

Using bitwise XOR '^' which does not check oddness.

To check if the least significant bit of 'b' is set (odd number), use bitwise AND '&' with 1.

4fill in blank

hard

Fill both blanks to create a function that returns the least common multiple (LCM) of two numbers using their GCD.

DSA C

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

int lcm(int a, int b) {
    return (a [1] b) / [2](a, b);
}

Drag options to blanks, or click blank then click option'

A*

B+

Cgcd

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication.

Dividing by a wrong function or variable.

The LCM of two numbers is their product divided by their GCD.

5fill in blank

hard

Fill all three blanks to create a function that counts how many numbers in an array are divisible by a given divisor.

DSA C

int count_divisible(int arr[], int size, int divisor) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] [1] divisor == [2]) {
            count [3];
        }
    }
    return count;
}

Drag options to blanks, or click blank then click option'

A%

B0

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using division '/' instead of modulo '%'.

Comparing to 1 instead of 0.

Using decrement '--' instead of increment.

To check divisibility, use modulo operator '%' and compare to 0. Increment count with '++'.