Interview Question

Power-of-a-Power.md

Power of a Power

Write a program to determine whether a number, n, is a power of 2^k.

clarification: n, k ≥ 0

Follow up: Can you do it with O(1) time and space complexity?

Examples

Input: n = 512, k = 3

Output: True

Explanation: 2³ = 8 and 8³ = 512.

Input: n = 1024, k = 4

Output: False

Explanation: 2⁴ = 16, and 1024 is not a power of 16.

Solution

Brute Force

We can calculate 2^k and then multiply it by itself multiple times, checking whether the current power is the number we are looking for.

def powerOfPower(n, k):
    ## the same as 2 ** k, potentially faster
    base = 1 << k
    curr = 1
    while curr < n:
        curr *= base
        if curr == n:
            return True
    return False

Time Complexity: O(log n); the variable curr grows exponentially.

Space Complexity: O(1).

Maths

We can determine whether or not a number is a power of two very quickly using bitwise operators:

def powerOfTwo(n):
    return n != 0 and n & n - 1 == 0

The trick, n & n - 1, gives us a number, n', which is n with its least significant bit removed. If n is a power of two, it will only have one bit, and so n' will be 0.

The next part comes from the following fact:

And numbers that are not powers of 2^k, namely 2^{m·k + i} for 1 ≤ i < k will have:

Leading us to our final implementation:

def powerOfPower(n, k):
    if n == 0:
        return False
    if n & n - 1 != 0:
        return False
    return n % (1 << k) - 1 == 1

Time Complexity: O(1).

Space Complexity: O(1).