Why Math and Number Theory Appear in DSA Problems in DSA Java - 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 Java

public static 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'

Ab

Ba

Ctemp

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using b % a instead of a % b

Using temp instead of a or b in modulo

Replacing b with 0 prematurely

In Euclid's algorithm, we replace b with a % 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 Java

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= [1]; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

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

An / 2

B(int) Math.sqrt(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

Not casting Math.sqrt(n) to int

To check primality efficiently, we test divisibility 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 Java

public static long modExp(long a, long b, long m) {
    long result = 1;
    a = a % m;
    while (b > 0) {
        if ((b & [1]) == 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return result;
}

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

A1

B0

C2

Db

Attempts:

3 left

💡 Hint

Common Mistakes

Using (b & 0) which is always 0

Using (b & 2) which checks the second bit

Using (b & b) which is always b

To check if the least significant bit of b is set, we use (b & 1) == 1.

4fill in blank

hard

Fill both blanks to create a map of numbers to their squares for numbers greater than 3.

DSA Java

Map<Integer, Integer> squares = new HashMap<>();
for (int num = 1; num <= 5; num++) {
    if (num [1] 3) {
        squares.put(num, num [2] num);
    }
}

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

A>

B<

C**

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the condition

Using '**' which is not valid in Java

Using '+' instead of '*' for squaring

We want numbers greater than 3, so use '>'. To square, use multiplication '*'.

5fill in blank

hard

Fill all three blanks to create a filtered map of uppercase keys to values greater than 10.

DSA Java

Map<String, Integer> filtered = new HashMap<>();
for (Map.Entry<String, Integer> entry : data.entrySet()) {
    if (entry.getValue() [1] 10) {
        filtered.put(entry.getKey().[2](), entry.getValue());
    }
}
int size = filtered.[3]();

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

A>

BtoUpperCase

Csize

DcontainsKey

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the condition

Using toLowerCase() instead of toUpperCase()

Using containsKey() instead of size() to get map size

We check if value > 10, convert key to uppercase with toUpperCase(), and get map size with size().

Practice

1. Why do many Data Structures & Algorithms problems involve concepts from math and number theory?

easy

A. Because math helps in optimizing algorithms and solving problems efficiently

B. Because math is only used for graphical user interfaces

C. Because number theory is unrelated to algorithms

D. Because math concepts slow down the algorithm

Solution

1. Step 1: Understand the role of math in algorithms

   Math provides tools to analyze and optimize algorithms, such as calculating time complexity and designing efficient solutions.

2. Step 2: Recognize number theory's importance

   Number theory concepts like primes, gcd, and modular arithmetic help solve problems involving divisibility, hashing, and cryptography.

3. Final Answer:

   Because math helps in optimizing algorithms and solving problems efficiently -> Option A

4. Quick Check:

   Math optimizes algorithms [OK]

Hint: Math often improves algorithm efficiency and correctness [OK]

Common Mistakes:

• Thinking math is only for UI or unrelated to algorithms
• Ignoring number theory's role in problem-solving
• Assuming math slows down algorithms

2. Which of the following Java code snippets correctly calculates the greatest common divisor (GCD) of two numbers using Euclid's algorithm?

easy

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

B. int gcd(int a, int b) { return a + b; }

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

D. int gcd(int a, int b) { return Math.min(a, b); }

Solution

1. Step 1: Check Euclid's algorithm logic

   Euclid's algorithm repeatedly replaces (a, b) with (b, a % b) until b becomes 0, then returns a.

2. Step 2: Verify each option

   int gcd(int a, int b) { while(b != 0) { int temp = b; b = a % b; a = temp; } return a; } correctly implements this loop and returns a. Others either add numbers, use wrong variables, or return min.

3. Final Answer:

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

4. Quick Check:

   Euclid's algorithm loop [OK]

Hint: Euclid's algorithm uses remainder until zero [OK]

Common Mistakes:

• Returning sum instead of gcd
• Mixing variable assignments incorrectly
• Using Math.min instead of gcd logic

3. What is the output of the following Java code?

public class Test {
  public static void main(String[] args) {
    int a = 12, b = 18;
    while (b != 0) {
      int temp = b;
      b = a % b;
      a = temp;
    }
    System.out.println(a);
  }
}

medium

A. 12

B. 3

C. 6

D. 18

Solution

1. Step 1: Trace Euclid's algorithm for gcd(12, 18)

   First iteration: temp=18, b=12%18=12, a=18
   Second iteration: temp=12, b=18%12=6, a=12
   Third iteration: temp=6, b=12%6=0, a=6

2. Step 2: Loop ends when b=0, print a

   Loop ends, a=6 is printed.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   gcd(12,18) = 6 [OK]

Hint: Trace Euclid's steps to find gcd [OK]

Common Mistakes:

• Confusing a and b updates
• Stopping loop too early
• Miscomputing remainder

4. The following Java method is intended to compute the modular exponentiation (a^b % mod). Find the error.

public static int modExp(int a, int b, int mod) {
  int result = 1;
  for (int i = 0; i < b; i++) {
    result = (result * a) % mod;
  }
  return result;
}

medium

A. It does not handle negative exponents

B. It forgets to take modulo after multiplication

C. It initializes result to 0 instead of 1

D. It uses a slow loop instead of fast exponentiation

Solution

1. Step 1: Understand the method's approach

   The method uses a simple loop multiplying 'a' b times, taking modulo each time.

2. Step 2: Identify inefficiency

   This approach is correct but slow for large b. Fast exponentiation uses repeated squaring to reduce time.

3. Final Answer:

   It uses a slow loop instead of fast exponentiation -> Option D

4. Quick Check:

   Simple loop is slow for large exponents [OK]

Hint: Use fast exponentiation for large powers [OK]

Common Mistakes:

• Thinking modulo is missing
• Ignoring performance issues
• Assuming negative exponents handled

5. You want to find the number of integers between 1 and 1000 that are divisible by 3 or 5 but not both. Which number theory concept helps solve this efficiently?

hard

A. Modular Inverse

B. Inclusion-Exclusion Principle

C. Euclid's Algorithm

D. Fermat's Little Theorem

Solution

1. Step 1: Understand the problem

   We want count of numbers divisible by 3 or 5 but not both, i.e., divisible by 3 XOR 5.

2. Step 2: Apply Inclusion-Exclusion Principle

   Count divisible by 3 + count divisible by 5 - 2 * count divisible by 15 (both) gives numbers divisible by 3 or 5 but not both.

3. Final Answer:

   Inclusion-Exclusion Principle -> Option B

4. Quick Check:

   Counting with overlaps = Inclusion-Exclusion [OK]

Hint: Use Inclusion-Exclusion to count overlapping sets [OK]

Common Mistakes:

• Counting divisible by 3 and 5 separately without overlap
• Using Euclid's algorithm incorrectly
• Confusing modular inverse with counting