Generalised solution to check whether a number is power of any 2^x in O(1) space, time


  • 0
    S

    To check whether a number is a power of a number 2^x, We have to ensure the following things:

    1. A number is power of two:
      We can do this by using the following:
      n&(n-1) == 0

    2. Also to check whether it is a power of 2^x, we could use the following expansion:
      a^n – b^n = (a – b)(a^(n – 1) + a^(n – 2) * b + a^(n – 3) b^2 + ··· + a * b^(n – 2) + b^(n – 1))
      Putting a = 2^x, b=1
      we get:
      (2^x)^n - 1 = (2^x-1) * [...]

    From this we can infer that if a number that is power of 2^x, then number-1 should also be divisible by (2^x-1)

    So using these two points together, we can verify whether the number is a power of 2^x or not in O(1) Time complexity and O(1) space complexity.

    For power of 4, we just have to check whether it is divisible by 3 or not.
    Similarly for 8, we check divisibility with 7, for 16 we check divisibility with 15, and so on.

    Hence the solution :

    bool isPowerOfFour(int num) {
            return num>0 && !(num&(num-1)) && !((num-1)%3);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.