Fast Exponentiation Power in Log N in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to multiply the result by base when exponent is odd.

DSA Rust

if n % 2 == 1 {
    result = result [1] base;
}

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

A-

B*

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of * causes wrong calculation.

Using / or - causes runtime errors or wrong results.

When exponent is odd, multiply the current result by base using the * operator.

2fill in blank

medium

Complete the code to halve the exponent n using integer division.

DSA Rust

n = n [1] 2;

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

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using * or + changes the exponent incorrectly.

Using - reduces exponent incorrectly.

Halving the exponent is done by integer division using / operator in Rust.

3fill in blank

hard

Fix the error in squaring the base inside the loop.

DSA Rust

base = base [1] base;

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

A*

B-

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using + or - results in wrong base update.

Using / causes runtime errors.

To square the base, multiply it by itself using * operator.

4fill in blank

hard

Fill both blanks to complete the while loop condition and the function return statement.

DSA Rust

while [1] > 0 {
    // loop body
}

return [2];

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

An

Bresult

Cbase

Dexponent

Attempts:

3 left

💡 Hint

Common Mistakes

Using base in loop condition causes infinite loop.

Returning base instead of result gives wrong output.

The loop runs while n > 0, and the function returns the accumulated result.

5fill in blank

hard

Fill all three blanks to complete the fast exponentiation function.

DSA Rust

fn fast_pow(mut base: i32, mut [1]: i32) -> i32 {
    let mut [2] = 1;
    while [1] > 0 {
        if [1] % 2 == 1 {
            [2] = [2] * base;
        }
        base = base * base;
        [1] = [1] / 2;
    }
    [2]
}

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

An

Bresult

Cexponent

Dpower

Attempts:

3 left

💡 Hint

Common Mistakes

Using inconsistent variable names causes errors.

Not initializing result to 1 causes wrong output.

The exponent variable is named 'exponent', result is stored in 'result', and the loop uses 'exponent'.

Practice

1. What is the main advantage of using fast exponentiation (power) algorithm over the simple repeated multiplication method?

easy

A. It reduces the time complexity from O(n) to O(log n)

B. It uses less memory than repeated multiplication

C. It works only for positive exponents

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand repeated multiplication time

   Repeated multiplication multiplies the base n times, so it takes O(n) time.

2. Step 2: Understand fast exponentiation time

   Fast exponentiation uses squaring and halves the exponent each step, so it takes O(log n) time.

3. Final Answer:

   It reduces the time complexity from O(n) to O(log n) -> Option A

4. Quick Check:

   Fast exponentiation = O(log n) [OK]

Hint: Fast exponentiation halves exponent each step [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Confusing time complexity with memory
• Believing it only works for positive exponents

2. Which of the following Rust function signatures correctly represents a fast exponentiation function for integers?

easy

A. fn fast_pow(base: i32, exp: i32) -> i32

B. fn fast_pow(base: i32, exp: i32) -> ()

C. fn fast_pow(base: i32) -> i32

D. fn fast_pow(exp: i32, base: i32) -> i32

Solution

1. Step 1: Check parameters needed

   Fast exponentiation needs base and exponent as inputs, both integers.

2. Step 2: Check return type

   It returns the computed power as an integer, so return type is i32.

3. Final Answer:

   fn fast_pow(base: i32, exp: i32) -> i32 -> Option A

4. Quick Check:

   Correct signature includes base, exp, returns i32 [OK]

Hint: Function needs base, exponent, returns result [OK]

Common Mistakes:

• Missing exponent parameter
• Wrong return type (void)
• Swapping parameter order incorrectly

3. What is the output of the following Rust code snippet?

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

fn main() {
    println!("{}", fast_pow(3, 5));
}

medium

A. 125

B. 243

C. 15

D. 81

Solution

1. Step 1: Understand fast_pow(3, 5)

   3^5 = 3*3*3*3*3 = 243.

2. Step 2: Trace the code logic

   Loop squares base and halves exp, multiplying result when exp is odd, correctly computing 243.

3. Final Answer:

   243 -> Option B

4. Quick Check:

   3^5 = 243 [OK]

Hint: Calculate 3^5 = 243 quickly [OK]

Common Mistakes:

• Calculating 5^3 instead of 3^5
• Confusing multiplication steps
• Forgetting to multiply result when exp is odd

4. Identify the bug in this Rust fast exponentiation function:

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

medium

A. The result should start at 0, not 1

B. The base should not be mutable

C. The loop should run while exp >= 0

D. The condition should check if exp % 2 == 1, not 0

Solution

1. Step 1: Check condition for multiplying result

   Multiplying result should happen when exp is odd (exp % 2 == 1), not even.

2. Step 2: Confirm other parts

   Mutable base is correct, result starts at 1, loop condition is correct.

3. Final Answer:

   The condition should check if exp % 2 == 1, not 0 -> Option D

4. Quick Check:

   Multiply result only when exp is odd [OK]

Hint: Multiply result only if exponent is odd [OK]

Common Mistakes:

• Multiplying when exponent is even
• Starting result at 0
• Loop running one extra time

5. You want to compute (2^30) % 1000 efficiently using fast exponentiation in Rust. Which modification is necessary to the standard fast exponentiation algorithm to handle this correctly?

hard

A. Increase the base to 1000 before starting

B. Use floating point numbers instead of integers

C. Add modulo operation after each multiplication to keep numbers small

D. Multiply result only when exponent is even

Solution

1. Step 1: Understand modulo exponentiation

   To compute (base^exp) % mod efficiently, apply modulo after each multiplication to avoid overflow.

2. Step 2: Modify fast exponentiation

   Insert modulo operation after multiplying result and squaring base to keep values within range.

3. Final Answer:

   Add modulo operation after each multiplication to keep numbers small -> Option C

4. Quick Check:

   Modulo after each step prevents overflow [OK]

Hint: Apply modulo after every multiplication [OK]

Common Mistakes:

• Using floats causing precision errors
• Not applying modulo each step causing overflow
• Incorrectly multiplying on even exponent