Pow(x, n) - Practice Coding Problems

Pow(x, n) - Problem

Math Recursion Medium

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

You need to handle both positive and negative exponents efficiently.

Note: Your solution should be more efficient than the naive approach of multiplying x by itself n times.

Input & Output

Example 1 — Positive Exponent

$ Input: x = 2.0, n = 10

› Output: 1024.0

💡 Note: 2^10 = 1024. Using binary exponentiation: 2^10 = (2^5)^2 = 32^2 = 1024

Example 2 — Negative Exponent

$ Input: x = 2.1, n = -2

› Output: 0.22676

💡 Note: 2.1^(-2) = 1/(2.1^2) = 1/4.41 ≈ 0.22676

Example 3 — Zero Exponent

$ Input: x = 2.0, n = 0

› Output: 1.0

💡 Note: Any number raised to power 0 equals 1

Constraints

-100.0 < x < 100.0
-2³¹ ≤ n ≤ 2³¹-1
-10⁴ ≤ xⁿ ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Base x and exponent n

Process

Use binary exponentiation instead of repeated multiplication

Output

x raised to the power n

Key Takeaway

🎯 Key Insight: Binary exponentiation reduces O(n) to O(log n) by repeatedly halving the exponent

Asked in

F Facebook 35 G Google 30 Li LinkedIn 25 a Amazon 20

The key insight is using binary exponentiation to reduce O(n) to O(log n). Instead of multiplying x by itself n times, we use the property x^n = (x^(n/2))^2 to halve the problem size. Best approach is iterative binary exponentiation with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Multiplication	O(n)	O(1)	Multiply x by itself n times using a simple loop
Iterative Binary Exponentiation	O(log n)	O(1)	Convert recursive solution to iterative using bit manipulation
Binary Exponentiation (Fast Power)	O(log n)	O(log n)	Use divide-and-conquer to calculate power in logarithmic time

Brute Force Multiplication — Algorithm Steps

Step 1: Handle negative exponent by converting to positive
Step 2: Multiply x by itself n times in a loop
Step 3: Return reciprocal if original exponent was negative

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set result = 1.0

Loop n times

Multiply result by x each iteration

Handle negatives

Take reciprocal if n was negative

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double solution(double x, int n) {
    if (n == 0) return 1.0;
    
    int isNegative = n < 0;
    long long absN = abs((long long)n);
    
    double result = 1.0;
    for (long long i = 0; i < absN; i++) {
        result *= x;
    }
    
    return isNegative ? 1.0 / result : result;
}

int main() {
    double x;
    int n;
    scanf("%lf", &x);
    scanf("%d", &n);
    
    double result = solution(x, n);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop runs n times, each iteration does constant work

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

120.0K Views

High Frequency

~15 min Avg. Time

4.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Multiplication — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler