Power(n, x)

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.

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.

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.

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

#include <iostream>
using namespace std;

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

int main() {
    cout << power(2, 10) << endl; // Output: 1024
    return 0;
}

def power(n, x):
    result = 1
    while x > 0:
        if x & 1:
            result *= n
        n *= n
        x >>= 1
    return result

# Example usage
print(power(2, 10))  # Output: 1024

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

    public static void main(String[] args) {
        System.out.println(power(2, 10)); // Output: 1024
    }
}

function power(n, x) {
  let result = 1;
  while (x > 0) {
    if (x & 1) {
      result *= n;
    }
    n *= n;
    x >>= 1;
  }
  return result;
}

// Example usage
console.log(power(2, 10)); // Output: 1024

package main

import "fmt"

func power(n int64, x uint) int64 {
    result := int64(1)
    for x > 0 {
        if x&1 == 1 {
            result *= n
        }
        n *= n
        x >>= 1
    }
    return result
}

func main() {
    fmt.Println(power(2, 10)) // Output: 1024
}

fn power(mut n: i64, mut x: u32) -> i64 {
    let mut result = 1;
    while x > 0 {
        if x & 1 == 1 {
            result *= n;
        }
        n *= n;
        x >>= 1;
    }
    result
}

fn main() {
    println!("{}", power(2, 10)); // Output: 1024
}

fun power(n: Long, x: Int): Long {
    var result = 1L
    var base = n
    var exponent = x
    while (exponent > 0) {
        if (exponent and 1 == 1) {
            result *= base
        }
        base *= base
        exponent = exponent shr 1
    }
    return result
}

fun main() {
    println(power(2, 10)) // Output: 1024
}

func power(_ n: Int, _ x: Int) -> Int {
    var result = 1
    var base = n
    var exponent = x
    while exponent > 0 {
        if exponent & 1 == 1 {
            result *= base
        }
        base *= base
        exponent >>= 1
    }
    return result
}

print(power(2, 10)) // Output: 1024

function power(n: number, x: number): number {
  let result = 1;
  while (x > 0) {
    if ((x & 1) === 1) {
      result *= n;
    }
    n *= n;
    x >>= 1;
  }
  return result;
}

// Example usage
console.log(power(2, 10)); // Output: 1024

Time complexity

Space complexity

O(1)

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.