Pow(x, n)

The problem

Return x raised to the power n without using your language's built-in power operator or function. x can be negative or have a decimal part. n is a whole number from -2,147,483,648 to 2,147,483,647. A negative power is 1 divided by the matching positive power, so 2 to the power -2 is 0.25, and x is never 0 when n is negative. Anything to the power 0 is 1, including 0. The tests accept an answer within 0.000000001 of the expected value, or within 0.000000001 times that value when it is larger than 1, ignoring signs.

What to write

function solve(x: number, n: number): number

Input
x = 2
n = 10

Output
1024

Input
x = 2.1
n = 3

Output
9.261

Constraints

Test results are finite.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   n can be as low as -2,147,483,648, and one test uses exactly that value. Multiplying by x once for every unit of n would be over two billion multiplications. The number of multiplications has to grow far more slowly than n does.

2. Hint 2: Ask a smaller question

   Suppose you have already worked out x to the power 4. What is the smallest number of extra multiplications that gets you x to the power 8? And from there to the power 16?

3. Hint 3: Name the pattern

   n is too large to count through, but squaring the base lets you halve the exponent. In binary (0s and 1s only), halving removes the last digit of n. A 1 means odd: one copy of the base goes to the answer first. Handling n one digit per round is digit-by-digit arithmetic. The method's usual name is exponentiation by squaring. Read the lesson on digit-by-digit arithmetic.

4. Hint 4: State the invariant

   One product never changes: the answer times the base raised to the exponent that is left. It starts as the result you want, with the answer at 1. Each round moves value out of the exponent and into the answer or the base. When the exponent left is 0, the answer is the whole result.

5. Hint 5: Sketch the pseudocode

   exponent = n without its sign. base = x, or 1 / x when n is negative. answer = 1. While exponent > 0: if exponent is odd, answer = answer × base. Then base = base × base, and exponent = exponent ÷ 2 rounded down. Return answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Repeatedly square the base and halve the exponent. Negative exponents use the reciprocal; avoid bitwise truncation for the minimum signed integer.

The slow way

Start at 1 and multiply by x, or by 1 / x when n is negative, once for every unit of n. It is correct, but one test has n = -2,147,483,648. That is over two billion multiplications, which takes seconds in JavaScript and far longer in Python. The method below needs 32 rounds.

The insight

Ten copies of x multiplied together are five copies of x × x. So squaring the base lets you halve the exponent. An odd exponent has one copy without a partner: multiply that copy into the answer, then halve what is left. Halving reaches 0 fast: an exponent of 2,147,483,648 is gone after 32 rounds.

Step by step

1. Use the size of n; a negative n turns the base into 1 / x. The size of n is n without its sign. A negative power is 1 divided by the positive power, which equals 1 / x, called the reciprocal of x, raised to that positive power.
2. Start the answer at 1. Multiplying by 1 changes nothing, so 1 is the neutral start for a product. It is also the final answer when n is 0, because the loop then never runs.
3. Go on while some of the exponent is left. One product stays the same all the way: the answer times the base raised to the exponent left. It starts as the result you want, and every round keeps it while the exponent shrinks.
4. Odd exponent: multiply the answer by the base once. An odd number of copies cannot all be paired. One copy moves into the answer, which leaves an even number. Odd or even is the exponent's last digit in binary, the notation that uses only 0s and 1s.
5. Square the base and halve the exponent, rounding down. Each pair of copies becomes one copy of the squared base, so half as many are needed. Rounding down drops the single copy that an odd exponent has already given to the answer.
6. No exponent is left: the answer is x to the power n. The product that never changed is now the answer times the base to the power 0, and anything to the power 0 is 1. So the answer alone is the result.

The same numbered steps are the comments in each solution.

function solve(x, n) {
    // 1. Use the size of n; a negative n turns the base into 1 / x
    let power = Math.abs(n);
    let base = n < 0 ? 1 / x : x;
    // 2. Start the answer at 1
    let result = 1;
    // 3. Go on while some of the exponent is left
    while (power > 0) {
        // 4. Odd exponent: multiply the answer by the base once
        if (power % 2 === 1)
            result *= base;
        // 5. Square the base and halve the exponent, rounding down
        base *= base;
        power = Math.floor(power / 2);
    }
    // 6. No exponent is left: the answer is x to the power n
    return result;
}

function solve(x: number, n: number): number {
  // 1. Use the size of n; a negative n turns the base into 1 / x
  let power = Math.abs(n);
  let base = n < 0 ? 1 / x : x;
  // 2. Start the answer at 1
  let result = 1;
  // 3. Go on while some of the exponent is left
  while (power > 0) {
    // 4. Odd exponent: multiply the answer by the base once
    if (power % 2 === 1) result *= base;
    // 5. Square the base and halve the exponent, rounding down
    base *= base;
    power = Math.floor(power / 2);
  }
  // 6. No exponent is left: the answer is x to the power n
  return result;
}

def solve(x, n):
    # 1. Use the size of n; a negative n turns the base into 1 / x
    power = abs(n)
    # float(x) turns a whole number into a float, the kind of number JavaScript
    # uses here, so both languages do the same arithmetic.
    base = 1 / x if n < 0 else float(x)
    # 2. Start the answer at 1
    result = 1.0
    # 3. Go on while some of the exponent is left
    while power > 0:
        # 4. Odd exponent: multiply the answer by the base once
        if power % 2 == 1:
            result *= base
        # 5. Square the base and halve the exponent, rounding down
        base *= base
        power //= 2
    # 6. No exponent is left: the answer is x to the power n
    return result

Example 1, traced

Input
x = 2
n = 10

Output
1024

Why it works

The answer times the base raised to the exponent left never changes. In example 1 it reads 1 × 2¹⁰, then 1 × 4⁵, 4 × 16², 4 × 256¹ and 1024 × 65536⁰: always 1024. An odd round moves one copy of the base into the answer, and squaring while halving regroups the rest. At exponent 0 only the answer remains.

Time and space

Time O(log |n|), extra space O(1). Every round halves the exponent. The number of halvings it takes to use a number up is about its logarithm, log for short, so the loop runs O(log |n|) times, where |n| is n without its sign: 32 rounds at most. Three numbers are stored, so the space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Deal with a negative n before the loop. If the loop runs on n itself, a negative exponent is never above 0, the loop does not start, and 2 to the power -2 comes back as 1 instead of 0.25.
• Round the halved exponent down. With plain division 5 becomes 2.5, and no later value is a whole odd number, so nothing more reaches the answer: 2 to the power 10 comes out as 4.
• In JavaScript, halve with Math.floor, not >>. The shift only handles whole numbers up to 2147483647: 2147483648 >> 1 is -1073741824, and the loop ends after one round. 2 to the power -2147483648, which rounds to 0, then returns 1.

Pattern

Digit-by-digit arithmetic. Builds on Binary Search and Happy Number.

Keep going