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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the remainder of division.

DSA Rust

let remainder = a [1] b;

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

A*

B/

C%

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using division operator instead of remainder operator.

The % operator gives the remainder after division.

2fill in blank

medium

Complete the code to check if a number is even.

DSA Rust

if num [1] 2 == 0 { println!("Even"); }

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

A/

B+

C*

D%

Attempts:

3 left

💡 Hint

Common Mistakes

Using division operator instead of remainder operator.

The remainder operator % with 2 checks if a number is even (remainder 0) or odd.

3fill in blank

hard

Fix the error in the code to compute the greatest common divisor (GCD) using Euclid's algorithm.

DSA Rust

fn gcd(mut a: i32, mut b: i32) -> i32 {
    while b != 0 {
        let temp = b;
        b = a [1] b;
        a = temp;
    }
    a
}

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

A%

B/

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using division instead of remainder causes infinite loop or wrong result.

Euclid's algorithm uses the remainder operator % to update b.

4fill in blank

hard

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

DSA Rust

let squares: std::collections::HashMap<_, _> = (1..10)
    .filter(|&x| x [1] 3)
    .map(|x| (x, x [2] x))
    .collect();

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

A>

B*

C<

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operator or addition instead of multiplication.

Filter numbers greater than 3 using > and square numbers using multiplication *.

5fill in blank

hard

Fill all three blanks to create a dictionary of uppercase letters mapped to their ASCII codes if code is greater than 65.

DSA Rust

let letters: std::collections::HashMap<_, _> = ('a'..='z')
    .map(|c| (c[1], c[3] as u8))
    .filter(|&(_, code)| code [2] 65)
    .collect();

println!("{:?}", letters);

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

A.to_ascii_uppercase()

B>

C<

D.to_ascii_lowercase()

Attempts:

3 left

💡 Hint

Common Mistakes

Using lowercase conversion or wrong comparison operator.

Convert character to uppercase with .to_ascii_uppercase(), filter codes greater than 65 with >.

Practice

1. Why do many data structure and algorithm problems involve concepts from math and number theory?

easy

A. Because math helps analyze problem constraints and optimize solutions

B. Because math is only used for graphical user interfaces

C. Because number theory is unrelated to algorithms

D. Because math slows down algorithm performance

Solution

1. Step 1: Understand the role of math in problem solving

   Math provides tools to analyze problem constraints, such as limits on input size and time complexity.

2. Step 2: Connect number theory to optimization

   Number theory concepts like divisibility and modular arithmetic help design efficient algorithms for common tasks.

3. Final Answer:

   Because math helps analyze problem constraints and optimize solutions -> Option A

4. Quick Check:

   Math aids optimization = A [OK]

Hint: Math helps understand and optimize algorithms fast [OK]

Common Mistakes:

• Thinking math is only for UI or unrelated to algorithms
• Ignoring math leads to inefficient solutions

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

easy

A. fn gcd(a: u32, b: u32) -> u32 { a - b }

B. fn gcd(mut a: u32, mut b: u32) -> u32 { while b != 0 { let t = b; b = a % b; a = t; } a }

C. fn gcd(a: u32, b: u32) -> u32 { a * b }

D. fn gcd(a: u32, b: u32) -> u32 { a + b }

Solution

1. Step 1: Identify Euclid's algorithm structure

   Euclid's algorithm repeatedly replaces (a, b) with (b, a % b) until b is zero.

2. Step 2: Check code correctness

   fn gcd(mut a: u32, mut b: u32) -> u32 { while b != 0 { let t = b; b = a % b; a = t; } a } correctly implements this loop with mutable variables and returns a when b is zero.

3. Final Answer:

   fn gcd(mut a: u32, mut b: u32) -> u32 { while b != 0 { let t = b; b = a % b; a = t; } a } -> Option B

4. Quick Check:

   Euclid's loop with modulo = D [OK]

Hint: Look for modulo and loop until remainder zero [OK]

Common Mistakes:

• Using addition or multiplication instead of modulo
• Not updating variables correctly in the loop

3. What is the output of this Rust code that uses modular exponentiation to compute (3^10) % 7?

fn mod_exp(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
    let mut result = 1;
    base %= modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exp /= 2;
    }
    result
}

fn main() {
    println!("{}", mod_exp(3, 10, 7));
}

medium

A. 4

B. 5

C. 6

D. 3

Solution

1. Step 1: Understand modular exponentiation steps

   Calculate 3^10 mod 7 using repeated squaring and modulo at each step.

2. Step 2: Trace calculation

   3^1=3 mod7=3; 3^2=9 mod7=2; 3^4=2^2=4; 3^8=4^2=2; Combine powers for 10=8+2: (3^8 * 3^2) mod7 = 2*2=4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   3^10 mod7 = 4 [OK]

Hint: Use repeated squaring and mod at each step [OK]

Common Mistakes:

• Calculating 3^10 directly without modulo
• Forgetting to apply modulo after multiplication

4. The following Rust function is intended to compute the least common multiple (LCM) of two numbers using their GCD. What is the bug?

fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}

fn lcm(a: u32, b: u32) -> u32 {
    a * b / gcd(a, b)
}

fn main() {
    println!("{}", lcm(0, 0));
}

medium

A. GCD function has infinite loop

B. No bug, code works correctly

C. LCM function returns zero always

D. Division by zero error when both inputs are zero

Solution

1. Step 1: Analyze gcd and lcm with zero input

   GCD(0,0) returns 0 since the while loop doesn't execute, causing LCM to compute 0*0/0, resulting in division by zero.

2. Step 2: Check for division by zero

   If both inputs are zero, gcd(0,0) returns 0, causing division by zero in LCM function.

3. Final Answer:

   Division by zero error when both inputs are zero -> Option D

4. Quick Check:

   LCM divides by gcd=0 causes error [OK]

Hint: Check zero inputs cause division by zero [OK]

Common Mistakes:

• Ignoring zero input edge cases
• Assuming gcd never returns zero

5. You want to find all prime numbers up to 30 efficiently in Rust. Which approach best uses number theory to solve this problem?

hard

A. Generate random numbers and test if they are prime

B. Check each number by dividing by all numbers less than itself

C. Use the Sieve of Eratosthenes algorithm to mark multiples as non-prime

D. Use a linked list to store numbers and remove non-primes manually

Solution

1. Step 1: Understand prime number generation methods

   Checking each number by trial division is slow; random testing is unreliable; linked list removal is inefficient.

2. Step 2: Identify efficient number theory algorithm

   The Sieve of Eratosthenes efficiently marks multiples of primes as non-prime, quickly finding all primes up to a limit.

3. Final Answer:

   Use the Sieve of Eratosthenes algorithm to mark multiples as non-prime -> Option C

4. Quick Check:

   Sieve method is fastest prime finder [OK]

Hint: Use sieve to mark multiples, not trial division [OK]

Common Mistakes:

• Using slow trial division for each number
• Relying on random checks without guarantees