Fast Exponentiation Power in Log N in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of fast exponentiation function

What is the output of this Rust function when computing 2 to the power 10?

DSA Rust

fn fast_pow(base: i32, exp: i32) -> i32 {
    if exp == 0 {
        return 1;
    }
    let half = fast_pow(base, exp / 2);
    if exp % 2 == 0 {
        half * half
    } else {
        half * half * base
    }
}

fn main() {
    println!("{}", fast_pow(2, 10));
}

A 1000

B 512

C 2048

D 1024

💡 Hint

Remember that 2^10 means multiplying 2 by itself 10 times.

The function uses fast exponentiation by dividing the exponent by 2 recursively. 2^10 equals 1024.

❓ Predict Output

intermediate

Output of fast exponentiation with odd exponent

What will be printed when running this Rust code for base=3 and exponent=5?

DSA Rust

fn fast_pow(base: i32, exp: i32) -> i32 {
    if exp == 0 {
        return 1;
    }
    let half = fast_pow(base, exp / 2);
    if exp % 2 == 0 {
        half * half
    } else {
        half * half * base
    }
}

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

A 15

B 125

C 243

D 81

💡 Hint

3^5 means 3 multiplied by itself 5 times.

3^5 = 3*3*3*3*3 = 243. The function correctly calculates this using recursion.

🔧 Debug

advanced

Identify the error in this fast exponentiation code

What error will this Rust code produce when compiled and run?

DSA Rust

fn fast_pow(base: i32, exp: i32) -> i32 {
    if exp == 0 {
        return 1;
    }
    let half = fast_pow(base, exp >> 1);
    if exp % 2 == 0 {
        half * half
    } else {
        half * half * base
    }
}

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

A Stack overflow due to infinite recursion

B Prints 0

C Prints 1

D Compiles and runs correctly printing 0.125

💡 Hint

Consider what happens when the exponent is negative.

The function does not handle negative exponents, so the recursive calls never reach the base case, causing infinite recursion and stack overflow.

❓ Predict Output

advanced

Output of fast exponentiation with zero exponent

What is the output of this Rust code when computing 5 to the power 0?

DSA Rust

fn fast_pow(base: i32, exp: i32) -> i32 {
    if exp == 0 {
        return 1;
    }
    let half = fast_pow(base, exp / 2);
    if exp % 2 == 0 {
        half * half
    } else {
        half * half * base
    }
}

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

A 1

B Error at runtime

C 5

D 0

💡 Hint

Any number to the power 0 is 1.

The base case returns 1 when exponent is 0, so the output is 1.

🧠 Conceptual

expert

Time complexity of fast exponentiation algorithm

What is the time complexity of the fast exponentiation algorithm implemented recursively as shown in previous examples?

A O(n) where n is the exponent

B O(log n) where n is the exponent

C O(1) constant time

D O(n^2) quadratic time

💡 Hint

The exponent is divided by 2 at each recursive call.

The algorithm reduces the exponent by half each time, so it runs in logarithmic time relative to the 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