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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fast Exponentiation Function

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;
}

#include <stdio.h>
int main() {
    printf("%d", fastPower(3, 5));
    return 0;
}

A 15

B 125

C 243

D 81

💡 Hint

Recall that 3^5 means 3 multiplied by itself 5 times.

3^5 = 3 * 3 * 3 * 3 * 3 = 243. The fast exponentiation algorithm efficiently computes this by squaring and multiplying selectively.

❓ Predict Output

intermediate

Result of Fast Power with Zero Exponent

What will be the output of this code snippet when calculating 5 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;
}

#include <stdio.h>
int main() {
    printf("%d", fastPower(5, 0));
    return 0;
}

A 0

B 1

C 5

D Undefined behavior

💡 Hint

Any number raised to the power 0 is 1.

By definition, any non-zero number raised to the power 0 equals 1. The function initializes result as 1 and does not enter the loop since exp is 0.

🔧 Debug

advanced

Identify the Error in Fast Exponentiation Code

What error will this code produce when compiled and run?

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;
}

#include <stdio.h>
int main() {
    printf("%d", fastPower(2, 10));
    return 0;
}

A Outputs 0

B Compilation error due to operator precedence

C Infinite loop

D Outputs 1024

💡 Hint

Check operator precedence in the condition inside the if statement.

The expression 'exp & 1 == 1' is parsed as 'exp & (1 == 1)', which is 'exp & 1' since == has higher precedence than &. The if (exp & 1) correctly evaluates to true for odd exp (exp & 1 == 1) and false for even. The code compiles and runs correctly, outputting 1024.

❓ Predict Output

advanced

Output of Recursive Fast Exponentiation

What is the output of this recursive fast exponentiation function when calculating 2 raised to the power 6?

DSA C

int fastPower(int base, int exp) {
    if (exp == 0) return 1;
    int half = fastPower(base, exp / 2);
    if (exp % 2 == 0) {
        return half * half;
    } else {
        return half * half * base;
    }
}

#include <stdio.h>
int main() {
    printf("%d", fastPower(2, 6));
    return 0;
}

A 64

B 8

C 16

D 32

💡 Hint

2^6 means 2 multiplied by itself 6 times.

2^6 = 64. The recursive function splits the exponent by half and multiplies accordingly.

❓ Predict Output

expert

Output of Fast Exponentiation with Negative Exponent Handling

What is the output of this modified fast exponentiation function that handles negative exponents by returning 0 for negative inputs, when called with base=2 and exp=-3?

DSA C

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

#include <stdio.h>
int main() {
    printf("%d", fastPower(2, -3));
    return 0;
}

A 0

B 1

C -8

D Undefined behavior

💡 Hint

The function returns 0 immediately for negative exponents.

The function checks if exponent is negative and returns 0 immediately, so output is 0.