Leetcode.com problem 50: "Pow(x,n)"

James S. Plank

Tue Aug 23 23:36:34 EDT 2022

Problem Statement.
A skeleton with a main() that reads problems from stdin.
tests.sh -- Testing script.
answers.txt -- Correct output of the testing script.
This is a "medium" problem.
Success Rate (as of August, 2022): 32.7%

In case Leetcode's servers are down

Implement the following method in the following class definition:

class Solution {
  public:
    double myPow(double x, int n);
};

Constraints:

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

The examples

UNIX> echo 2 10 | a.out
1024
UNIX> echo 2.1 3 | a.out
9.261
UNIX> echo 2 -2 | a.out
0.25
UNIX>

Hints

Let's suppose that n equals 11 and look at n in binary: 1011. You can confirm that:

x¹¹ = x⁸ * x² * x¹

x¹¹ = x^2³ * x^2¹ * x^2⁰

Does that give you enough information to solve the problem? Let's do another example -- suppose that x is 1.000001 and n is 2326. In hex, n is 0x916, so in binary, n is 1001 0001 0110.

Now, let's take a look at x^2ⁱ for 1 from 0 to 11:

x^2⁰: 1.000001
x^2¹: 1.000002
x^2²: 1.000004
x^2³: 1.000008
x^2⁴: 1.000016
x^2⁵: 1.000032
x^2⁶: 1.000064
x^2⁷: 1.000128
x^2⁸: 1.000256
x^2⁹: 1.000512
x^2¹⁰: 1.001025
x^2¹¹: 1.002050

You'll note that you can calculate each of these values from the previous value with one multiplication. So, using the binary format of n:

x^0x916 = x^2¹¹ * x^2⁸ * x^2⁴ * x^2² * x^2¹

1.002050 * 1.000256 * 1.000016 * 1.000004 * 1.000002 = 1.002329

UNIX> echo 1.000001 2326 | a.out
1.00233
UNIX>

You'll need to treat negative exponents differently, and since n can be -2³¹ but 2³¹ does not fit into an int, you'll do best to use long long's instead of ints. I'm pretty sure that this is the reason why the acceptance rate is so low.