Loading…

easyBasicsSometimes asked

Power of a Number

Basics · 6 min

Given a base x and a non-negative exponent n, compute xⁿ (assume the result fits in a 64-bit integer).

In plain English

Fast exponentiation: square the base and halve the exponent, multiplying into the result on odd bits — O(log n) instead of O(n).

Examples

Example 1

Input: x = 2, n = 10
Output: 1024
Note: 2¹⁰ = 1024.

Example 2

Input: x = 5, n = 0
Output: 1
Note: Anything⁰ = 1.

Example 3

Input: x = 3, n = 3
Output: 27
Note: 3³ = 27.

Constraints

0 ≤ n ≤ 62, result fits in long

Clarifying questions2First question: Is the exponent non-negative?Explore questions

Q1.Is the exponent non-negative?
I'll assume n ≥ 0; negative n means 1/xⁿ (a double result).
Q2.Do I need it modulo something?
If so, take the modulus after each multiply — modular exponentiation.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use binary exponentiation: while `n > 0`, if `n` is odd multiply the answer by `x`, then square `x` and halve `n`. O(log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know binary exponentiation and can connect it to the exponent's bits.

Where candidates slip

A linear loop, or only squaring without the odd-bit multiply.

How to stand out

Generalise to modular exponentiation (`% mod` each multiply) used in hashing/crypto.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Fast (binary) exponentiation

TimeO(log n)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A loop multiplying x n times is O(n). Can you use the binary form of n?

2Hint 2Explore hint

Squaring gives x, x², x⁴, x⁸… — multiply in the ones matching n's 1-bits.

3Hint 3Explore hint

If n is odd, fold x into the result; then square x and halve n.

A · Core idea

Binary (fast) exponentiation computes xⁿ in O(log n) multiplications instead of the O(n) of a naive loop, by exploiting the binary representation of the exponent.

The core idea. Repeatedly squaring the base produces x¹, x², x⁴, x⁸, … — the powers of x at each bit position. Write n in binary; xⁿ is the product of exactly those squared powers where n has a 1-bit. So scan n bit by bit: if the current bit is 1, multiply it into the result; either way, square the base and shift n right.

Why this is log n. Each step halves n (n >>= 1), so there are about log₂(n) iterations, each doing a constant number of multiplications. For n = 1,000,000 that's ~20 multiplies versus a million.

The base case. x⁰ = 1, handled because the loop runs zero times and the result starts at 1. A simple O(n) loop is acceptable for small n, but showing the O(log n) trick is the distinguishing move.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 3, n = 5 (binary 101)

n=5 (odd)

result *= 3 → 3; x = 9; n = 2

Stateresult 3

Final result243

C · Code with teaching comments

solution.javaJava

Fast (binary) exponentiation — optimal

2 teaching notes

1
public long power(long x, int n) {
2
    long result = 1;
3
    while (n > 0) {
4
        // Multiply in the current power of x when this exponent bit is set.
5
        if ((n & 1) == 1) result *= x;
6
        x *= x;
7
        n >>= 1;
8
    }
9
    return result;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

A simple O(n) loop is acceptable, but showing the O(log n) trick is what distinguishes a strong answer.

ComplexityO(log n) time, O(1) space — the exponent halves each iteration, so ~log₂(n) iterations with O(1) work each.

E · Edge cases and pitfalls5x = 5, n = 0 — Loop never runs; result stays 1 (5⁰ = 1).Explore edge cases

Edge cases handled

x = 5, n = 0Loop never runs; result stays 1 (5⁰ = 1).
x = 2, n = 10Five-ish steps give 1024 with far fewer multiplies than 10.
x = 1, n = 1000000Returns 1 quickly; squaring 1 stays 1.

Pitfalls

Using an O(n) loop when O(log n) is expected.
Forgetting x⁰ = 1, or not squaring x every iteration.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long power(long x, int n) { long result = 1; while (n > 0) { if ((n & 1) == 1) result *= x; x *= x;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning 0 for n = 0 instead of 1.
Writing an O(n) loop when O(log n) is expected.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary exponentiation

Code pattern to memorize

res=1; while n>0: if n&1: res*=x; x*=x; n>>=1

Rules to remember

1result starts at 1.
2Odd bit → multiply; always square base, shift n.
3O(log n) multiplications.

Use this pattern when

x^n fast
Modular exponentiation
Matrix power / repeated squaring

Choose another pattern when

n tiny — a plain loop is fine and clearer

Interview takeaway

Square-and-multiply turns power, modpow, and matrix power into log time.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Binary exponentiation. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Pow(x, n) with negatives
Coming soon
Handle negative exponents and double precision.
Modular Exponentiation
Coming soon
Same loop, take `% mod` after each multiply.

Same pattern

easyBasicsSometimes asked

Power of a Number

Basics · 6 min

Given a base x and a non-negative exponent n, compute xⁿ (assume the result fits in a 64-bit integer).

In plain English

Fast exponentiation: square the base and halve the exponent, multiplying into the result on odd bits — O(log n) instead of O(n).

Examples

Example 1

Input: x = 2, n = 10
Output: 1024
Note: 2¹⁰ = 1024.

Example 2

Input: x = 5, n = 0
Output: 1
Note: Anything⁰ = 1.

Example 3

Input: x = 3, n = 3
Output: 27
Note: 3³ = 27.

Constraints

0 ≤ n ≤ 62, result fits in long

Clarifying questions2First question: Is the exponent non-negative?Explore questions

Q1.Is the exponent non-negative?
I'll assume n ≥ 0; negative n means 1/xⁿ (a double result).
Q2.Do I need it modulo something?
If so, take the modulus after each multiply — modular exponentiation.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use binary exponentiation: while `n > 0`, if `n` is odd multiply the answer by `x`, then square `x` and halve `n`. O(log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know binary exponentiation and can connect it to the exponent's bits.

Where candidates slip

A linear loop, or only squaring without the odd-bit multiply.

How to stand out

Generalise to modular exponentiation (`% mod` each multiply) used in hashing/crypto.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Fast (binary) exponentiation

TimeO(log n)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A loop multiplying x n times is O(n). Can you use the binary form of n?

2Hint 2Explore hint

Squaring gives x, x², x⁴, x⁸… — multiply in the ones matching n's 1-bits.

3Hint 3Explore hint

If n is odd, fold x into the result; then square x and halve n.

A · Core idea

Binary (fast) exponentiation computes xⁿ in O(log n) multiplications instead of the O(n) of a naive loop, by exploiting the binary representation of the exponent.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 3, n = 5 (binary 101)

n=5 (odd)

result *= 3 → 3; x = 9; n = 2

Stateresult 3

Final result243

C · Code with teaching comments

solution.javaJava

Fast (binary) exponentiation — optimal

2 teaching notes

1
public long power(long x, int n) {
2
    long result = 1;
3
    while (n > 0) {
4
        // Multiply in the current power of x when this exponent bit is set.
5
        if ((n & 1) == 1) result *= x;
6
        x *= x;
7
        n >>= 1;
8
    }
9
    return result;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

A simple O(n) loop is acceptable, but showing the O(log n) trick is what distinguishes a strong answer.

ComplexityO(log n) time, O(1) space — the exponent halves each iteration, so ~log₂(n) iterations with O(1) work each.

E · Edge cases and pitfalls5x = 5, n = 0 — Loop never runs; result stays 1 (5⁰ = 1).Explore edge cases

Edge cases handled

x = 5, n = 0Loop never runs; result stays 1 (5⁰ = 1).
x = 2, n = 10Five-ish steps give 1024 with far fewer multiplies than 10.
x = 1, n = 1000000Returns 1 quickly; squaring 1 stays 1.

Pitfalls

Using an O(n) loop when O(log n) is expected.
Forgetting x⁰ = 1, or not squaring x every iteration.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long power(long x, int n) { long result = 1; while (n > 0) { if ((n & 1) == 1) result *= x; x *= x;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning 0 for n = 0 instead of 1.
Writing an O(n) loop when O(log n) is expected.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary exponentiation

Code pattern to memorize

res=1; while n>0: if n&1: res*=x; x*=x; n>>=1

Rules to remember

1result starts at 1.
2Odd bit → multiply; always square base, shift n.
3O(log n) multiplications.

Use this pattern when

x^n fast
Modular exponentiation
Matrix power / repeated squaring

Choose another pattern when

n tiny — a plain loop is fine and clearer

Interview takeaway

Square-and-multiply turns power, modpow, and matrix power into log time.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Binary exponentiation. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Pow(x, n) with negatives
Coming soon
Handle negative exponents and double precision.
Modular Exponentiation
Coming soon
Same loop, take `% mod` after each multiply.

Same pattern