Challenge - 5 Problems
Number Theory Mastery in DSA
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of GCD Calculation in a Loop
What is the output of this C# code that calculates the GCD of pairs of numbers in an array?
DSA C#
using System; class Program { static int GCD(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } static void Main() { int[] nums = {24, 36, 48}; for (int i = 0; i < nums.Length - 1; i++) { Console.Write(GCD(nums[i], nums[i+1]) + " "); } } }
Attempts:
2 left
💡 Hint
Recall that GCD finds the largest number dividing both numbers without remainder.
✗ Incorrect
The GCD of 24 and 36 is 12, and the GCD of 36 and 48 is also 12. So the output prints "12 12 ".
🧠 Conceptual
intermediate1:30remaining
Why Use Modular Arithmetic in DSA?
Why is modular arithmetic commonly used in data structures and algorithms problems?
Attempts:
2 left
💡 Hint
Think about what happens when numbers get very large in calculations.
✗ Incorrect
Modular arithmetic keeps numbers within a fixed range, preventing overflow and allowing efficient calculations especially in hashing and combinatorics.
🔧 Debug
advanced2:00remaining
Find the Bug in Prime Checking Code
What error does this C# code produce when checking if a number is prime?
DSA C#
using System; class Program { static bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= n / 2; i++) { if (n % i == 0) return false; } return true; } static void Main() { Console.WriteLine(IsPrime(2)); } }
Attempts:
2 left
💡 Hint
Check the loop condition carefully for small inputs.
✗ Incorrect
The loop runs from i=2 to i <= n/2. For n=2, n/2 is 1, so the loop does not run. The function returns true correctly. But for n=4, it misses checking divisor 2. However, the question asks about input 2, which returns true correctly. So the bug is that the loop should run up to i <= sqrt(n) or i <= n/2 inclusive. The code incorrectly returns true for some composite numbers but not for 2. The question asks about error for input 2, so the answer is that it outputs true correctly.
❓ Predict Output
advanced2:00remaining
Output of Fibonacci Modulo Calculation
What is the output of this C# code that calculates Fibonacci numbers modulo 10?
DSA C#
using System; class Program { static int FibMod(int n) { if (n <= 1) return n; int a = 0, b = 1, c = 0; for (int i = 2; i <= n; i++) { c = (a + b) % 10; a = b; b = c; } return c; } static void Main() { Console.WriteLine(FibMod(15)); } }
Attempts:
2 left
💡 Hint
Calculate Fibonacci numbers up to 15 and take modulo 10.
✗ Incorrect
The 15th Fibonacci number is 610. 610 % 10 = 0. But indexing starts at 0: Fib(0)=0, Fib(1)=1, so Fib(15) is the 15th number starting from 0. The code returns Fib(15) mod 10 = 610 mod 10 = 0. So output is 0.
🧠 Conceptual
expert2:30remaining
Why Are Number Theory Concepts Important in DSA?
Which of these is the best reason why number theory concepts appear often in data structures and algorithms problems?
Attempts:
2 left
💡 Hint
Think about how properties like divisibility can simplify calculations.
✗ Incorrect
Number theory provides tools like modular arithmetic, prime factorization, and divisibility rules that help reduce complexity and optimize algorithms in many DSA problems.