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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of fast exponentiation with positive exponent

What is the output of the following C++ code that calculates 3 raised to the power 5 using fast exponentiation?

DSA C++

int fastPower(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    return result;
}

int main() {
    int res = fastPower(3, 5);
    std::cout << res << std::endl;
    return 0;
}

A 243

B 125

C 15

D 81

💡 Hint

Recall that 3^5 = 3 * 3 * 3 * 3 * 3

The fast exponentiation correctly computes 3^5 = 243 by multiplying base when exponent bit is set and squaring base each iteration.

❓ Predict Output

intermediate

Output when exponent is zero

What will the following code print when calculating 10 raised to the power 0 using fast exponentiation?

DSA C++

int fastPower(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    return result;
}

int main() {
    int res = fastPower(10, 0);
    std::cout << res << std::endl;
    return 0;
}

A 0

B Undefined behavior

C 1

D 10

💡 Hint

Any number raised to the power 0 is 1.

The function initializes result to 1 and since exponent is zero, the loop does not run, so it returns 1.

❓ Predict Output

advanced

Output of fast exponentiation with negative exponent (integer version)

What will the following code output when calculating 2 raised to the power -3 using the given fast exponentiation function?

DSA C++

int fastPower(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    return result;
}

int main() {
    int res = fastPower(2, -3);
    std::cout << res << std::endl;
    return 0;
}

A Undefined behavior (infinite loop or wrong result)

B 1

C 0

D -8

💡 Hint

Consider how the while loop condition handles negative exponents.

The loop condition exp > 0 is false initially for negative exponent, so the loop never runs and the function returns 1, which is incorrect for negative powers. This is a logical error.

🧠 Conceptual

advanced

Time complexity of fast exponentiation

What is the time complexity of the fast exponentiation algorithm that calculates base^exp by repeatedly squaring and multiplying when needed?

A O(n), where n is the exponent

B O(1), constant time

C O(n^2), where n is the exponent

D O(log n), where n is the exponent

💡 Hint

Think about how the exponent is reduced each step.

The exponent is divided by 2 each iteration, so the number of steps is proportional to log base 2 of the exponent.

🔧 Debug

expert

Identify the bug in this fast exponentiation code

What error will this C++ code produce when trying to compute 2^10 using fast exponentiation?

DSA C++

int fastPower(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if ((exp & 1) = 1) {
            result *= base;
        }
        base *= base;
        exp >>= 1;
    }
    return result;
}

int main() {
    int res = fastPower(2, 10);
    std::cout << res << std::endl;
    return 0;
}

A Outputs 1024 correctly

B Compilation error due to operator precedence

C Always outputs 1

D Infinite loop

💡 Hint

Check the condition inside the if statement carefully.

The expression 'exp & 1 = 1' is parsed as (exp & 1) = 1 because the bitwise & operator has higher precedence than assignment =. However, (exp & 1) is an rvalue and cannot be assigned to, resulting in a compilation error: 'lvalue required as left operand of assignment'. The intended condition should be 'exp & 1 == 1'.

Practice

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

easy

A. It works only for positive exponents

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

C. It uses less memory by storing intermediate results

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand simple exponentiation time

   Simple repeated multiplication takes n multiplications for power n, so O(n) time.

2. Step 2: Analyze fast exponentiation time

   Fast exponentiation splits power by half each step, reducing steps to about log n, so O(log n) time.

3. Final Answer:

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

4. Quick Check:

   Fast exponentiation = O(log n) [OK]

Hint: Fast exponentiation halves power each step [OK]

Common Mistakes:

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

2. Which of the following is the correct base case for a recursive fast exponentiation function computing x^n?

easy

A. if (x == 0) return 0;

B. if (x == 1) return n;

C. if (n == 1) return 0;

D. if (n == 0) return 1;

Solution

1. Step 1: Identify base case for exponent zero

   Any number to the power 0 is 1, so if n == 0, return 1.

2. Step 2: Check other options

   Other options do not correctly represent the base case for power calculation.

3. Final Answer:

   if (n == 0) return 1; -> Option D

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Power zero always returns 1 [OK]

Common Mistakes:

• Returning 0 for n=1
• Confusing base case with input x values
• Returning n instead of 1 for base case

3. What is the output of the following C++ code snippet?

int fastPow(int x, int n) {
    if (n == 0) return 1;
    int half = fastPow(x, n / 2);
    if (n % 2 == 0) return half * half;
    else return half * half * x;
}

int main() {
    std::cout << fastPow(2, 5);
    return 0;
}

medium

A. 32

B. 16

C. 25

D. 10

Solution

1. Step 1: Trace recursive calls for fastPow(2,5)

   fastPow(2,5) calls fastPow(2,2), which calls fastPow(2,1), which calls fastPow(2,0)=1.

2. Step 2: Calculate values bottom-up

   fastPow(2,1) = 1*1*2=2; fastPow(2,2) = 2*2=4; fastPow(2,5) = 4*4*2=32.

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember odd powers multiply extra x once [OK]

Common Mistakes:

• Calculating 2^5 as 16 by missing odd case
• Confusing multiplication order
• Forgetting base case returns 1

4. The following code attempts to implement fast exponentiation but has a bug. What is the bug?

int fastPow(int x, int n) {
    if (n == 0) return 1;
    int half = fastPow(x, n / 2);
    if (n % 2 == 0) return half * half;
    else return half * half * n;
}

medium

A. Multiplying by n instead of x in the odd case

B. Missing base case for n == 1

C. Using integer division incorrectly

D. Not handling negative powers

Solution

1. Step 1: Check odd power multiplication

   In the odd case, code multiplies by n instead of x, which is incorrect.

2. Step 2: Confirm correct multiplication

   It should multiply by x to account for the extra factor in odd powers.

3. Final Answer:

   Multiplying by n instead of x in the odd case -> Option A

4. Quick Check:

   Odd power multiply by x, not n [OK]

Hint: Multiply by base x, not exponent n, for odd powers [OK]

Common Mistakes:

• Confusing n and x in multiplication
• Thinking base case missing causes this bug
• Ignoring negative power handling

5. You want to compute (3^13) % 7 efficiently using fast exponentiation with modulo. Which of the following code snippets correctly implements this?

hard

A. int modPow(int x, int n, int m) {
if (n == 0) return 1;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 0) return (halfSq * x) % m;
else return halfSq;
}

B. int modPow(int x, int n, int m) {
if (n == 0) return 0;
int half = modPow(x, n / 2, m);
int halfSq = (half + half) % m;
if (n % 2 == 0) return halfSq;
else return (halfSq * x) % m;
}

C. int modPow(int x, int n, int m) {
if (n == 0) return 1;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 1) return (halfSq * x) % m;
else return halfSq;
}

D. int modPow(int x, int n, int m) {
if (n == 1) return x % m;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 1) return halfSq;
else return (halfSq * x) % m;
}

Solution

1. Step 1: Check base case and modulo usage

   Base case returns 1 for n=0, correct. Multiplications use modulo to avoid overflow.

2. Step 2: Verify odd and even power handling

   For odd n, multiply halfSq by x modulo m; for even n, return halfSq. int modPow(int x, int n, int m) { if (n == 0) return 1; int half = modPow(x, n / 2, m); int halfSq = (half * half) % m; if (n % 2 == 1) return (halfSq * x) % m; else return halfSq; } matches this logic correctly.

3. Final Answer:

   code correctly implements fast exponentiation with modulo -> Option C

4. Quick Check:

   Modulo applied after each multiplication [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Returning 0 for base case
• Using addition instead of multiplication
• Swapping odd and even cases