Home Pow(x, n)
Post
Cancel

LeetCode #50: Pow(x, n) (C/C++).

medium

source: https://leetcode.com/problems/powx-n/
C/C++ Solution to LeetCode problem 50. Pow(x, n).

Problem


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

Examples


Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints


  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n is an integer.
  • -104 <= xn <= 104

Solution


Instead of multiplying by x n-times we will optimize (reduce the amount of times we multiply) using the right-shift bitwise operation.

  • We initialize our result = 1.
  • While n > 0 (we use the absolute value of n).
  • If the last (LSB) of n is 1 we multiply result * x.
  • We multiply x by itself (x * x).
  • And right-shift n (n >> 1).
  • Finally, if the original n<0, then the result will be 1/result otherwise result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
  double myPow(double x, int n) {
    double ans = 1.0;
    bool neg = n < 0;
    n = abs(n);
    while (n > 0) {
      if (n & 1)
        ans = ans * x;
 
      x = x * x;
      n = n >> 1;
    }

    return neg ? 1 / ans: ans;
  }
};
This post is licensed under CC BY 4.0 by the author.

Rotate Image

N-Queens