Compute Power(n, x) - Visualization

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given two integers n and x, your task is to compute nx — that is, raise n to the power of x.

You should implement an efficient solution, preferably using the Binary Exponentiation method.

Assume x is a non-negative integer.

Examples❯

n x Output Description
2 3 8 2 raised to power 3 is 2 * 2 * 2 = 8
5 0 1 Any number to the power 0 is 1
0 5 0 0 raised to any positive power is 0
1 100 1 1 to any power is always 1
2 10 1024 Using binary exponentiation: 210 = 1024
-2 4 16 Even power of a negative number is positive: (-2)^4 = 16
-2 3 -8 Odd power of a negative number remains negative: (-2)^3 = -8
99999 0 1 Edge case: large base but zero exponent results in 1
"" 3 0 Empty base input treated as 0 → 03 = 0
2 "" 1 Empty exponent treated as 0 → 20 = 1

Solution❯

Understanding the Problem

We are given two integers: n and x. Our goal is to calculate nx, which means multiplying n with itself x times.

For example, if n = 2 and x = 5, the answer is 2 * 2 * 2 * 2 * 2 = 32.

A simple approach is to multiply n x times, but that takes linear time. Instead, we want an efficient method — Binary Exponentiation, which reduces the time to O(log x).

Step-by-Step Solution with Example

step 1: Understand the core idea of Binary Exponentiation

Instead of multiplying n repeatedly, we exploit the binary nature of the exponent. We split the power based on whether it is odd or even.

  • If x is even, then nx = (nx/2)2
  • If x is odd, then nx = n × nx-1

step 2: Start with initial values

n = 2  
x = 5  
result = 1

step 3: Apply the loop while x > 0

We keep squaring n and halving x. If x is odd at any point, we multiply result by n.

step 4: Walk through example (n = 2, x = 5)

Iteration 1:
x = 5 (odd) → result *= n → result = 1 * 2 = 2  
n = n * n = 2 * 2 = 4  
x = x // 2 = 5 // 2 = 2

Iteration 2:
x = 2 (even) → result remains 2  
n = n * n = 4 * 4 = 16  
x = x // 2 = 2 // 2 = 1

Iteration 3:
x = 1 (odd) → result *= n → result = 2 * 16 = 32  
n = n * n = 16 * 16 = 256  
x = x // 2 = 1 // 2 = 0

Loop ends. Final result = 32

Edge Cases

  • x = 0: Any number raised to the power of 0 is 1 (except when n = 0).
  • n = 0 and x = 0: This is mathematically undefined but usually treated as 1 in programming.
  • n = 0 and x > 0: Always returns 0.
  • Large x: Binary Exponentiation handles large exponents efficiently in logarithmic time.

Algorithm Steps❯

  1. Initialize result = 1.
  2. While x > 0:
    • If x is odd, multiply result *= n.
    • Square n → n *= n.
    • Divide x by 2 → x //= 2.
  3. Return result as the final answer.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

long long power(long long n, unsigned int x) {
    long long result = 1;
    while (x > 0) {
        if (x & 1) {
            result *= n;
        }
        n *= n;
        x >>= 1;
    }
    return result;
}

int main() {
    long long n = 2;
    unsigned int x = 10;
    printf("%lld\n", power(n, x)); // Output: 1024
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(log x)Binary exponentiation reduces the power x by half in each step, leading to logarithmic time complexity. Even if x is 0, the algorithm performs a constant number of operations.
Average CaseO(log x)In the average case, the number of iterations depends on the number of bits in x. For each bit, we either multiply the result or square the base, which is logarithmic in terms of x.
Worst CaseO(log x)In the worst case, where x has the maximum number of bits set (e.g., x = 2^k - 1), we still only perform O(log x) multiplications and squarings, maintaining logarithmic time complexity.

Space Complexity❯

O(1)

Explanation: The algorithm uses only a constant amount of extra space — variables to hold the result, base, and exponent. No additional memory is used that depends on the input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...