DP example for "Power of Two" in Python

Question

I'm not familiar with Python but want to provide a code snippet for an SO question about Dynamic Programming.

The snippet should show the bottom-up approach of DP.

The function isPowerOfTwo returns True if the given number n is a power of two otherwise False. The implementation uses a button-up table results.

def isPowerOfTwo(n):
    results = {}
    for i in range(1, n + 1):
        if i == 2:
            results[i] = True
        elif i % 2 != 0:
            results[i] = False
        else:
            results[i] = results[i/2]
    return results[n]

Do you have any recommendations?

Answer 1

There are some major issues with your approach, the major one being that it is going to terribly break down for really large numbers. But if you want to go with it, here are a couple of improvements:

1. Don't use a dictionary. If your indices are consecutive integers, then a list is the right data structure.

2. You already know that most of your entries are going to be False, so why not initialize those in bulk and worry only about setting the Trues?

   def is_power_of_two(n):
       sieve = [False] * (n + 1)
       pot = 2
       while pot < len(sieve):
           sieve[pot] = True
           pot *= 2
       return sieve[n]
   

The name sieve is taken from the approach being somewhat similar to the sieve of Erathostenes algorithm.

In your case you can take things one step further, and rather than storing the full array, store only the indices of the True entries:

def is_power_of_two(n):
    pots = [2]
    while pots[-1] < n:
        pots.append(pots[-1]*2]
    return pots[-1] == n

If you look at that code, you don't really need to store the whole array, since you are only using the last value. So you can get the same time complexity, \$O(\log n)\$, but with constant space, by doing:

def is_power_of_two(n):
    pot = 2
    while pot < n:
        pot *= 2
    return pot == n

Of course the proper, fast way of checking if a number is a power of two is with a little bit twiddling hack that give \$O(1)\$ performance:

def is_power_of_two(n):
    return not n & (n - 1)

Answer 2

If someone were to say: isPowerOf2(9223372036854775808) what would your function do?

For a start, it will end up with an array of a very, very large size.... that can't be right....

... next, computers are binary machines, and binary numbers are powers of 2.... there has to be a way for the base infrastructure to make that easier? Well, there is.

When written in binary, these are the first few powers of 2:

00000001 - 1 ( 2^0 )
00000010 - 2 ( 2^1 )
00000100 - 4 ( 2^2 )
00001000 - 8 ( 2^3 )
00010000 - 16 ( 2^4 )
00100000 - 32 ( 2^5 )
01000000 - 64 ( 2^6 )
10000000 - 128 ( 2^7 )
...

Notice, that, in binary, all powers of 2 have exactly one 1 bit set?

So, your function should be able to take advantage of that... how about:

def isPowerOfTwo(n):
    return bin(n).count("1") == 1

Convert the input number to binary representation in a String, and if just one bit is set, it's a power of 2.

That removes all the extra memory needed for the results, and it only needs to create a String that is a size which is logarithmic to the input value.... which is quite small, even for very large input values.

There's probably faster ways to implement that algorithm, but the core concept is good: just count the set bits, and if there's 1, it's a power of 2.

Answer 3

The best idea is going built-in with the functools module:

import functools

@functools.lru_cache(maxsize=None)
def is_power2(n):
    if n == 1: return True
    if n % 2 != 0: return False
    return is_power2(n // 2)

Answer 4

Here is a solution that I'd consider a bottom-up dynamic programming solution.

powersOfTwo = set([1]) # used to store all necessary powers of two

# returns max(powersOfTwo) but in O(1)
def highestPowerOfTwo():
    return 2 ** (len(powersOfTwo) - 1)

def isPowerOfTwo(n):
    # ensure our set of powers of 2 is large enough
    while n > highestPowerOfTwo():
        powersOfTwo.add(2 * highestPowerOfTwo())  # add the next power of 2

    return n in powersOfTwo  # look up whether it is a power of two


print isPowerOfTwo(2**1002 + 1) # False
print isPowerOfTwo(2**63)       # True

This solution builds a set of powers of two starting at 1 and finding the next power of two by doubling it. This is repeated until \$n\$ is less than the maximum value in the set. Then we just look whether \$n\$ is in the set of powers of two.

If \$n\$ is in the set it is a power of two. If \$n\$ is not in the set it can't be a power of two as it is not in the set of all power of two up to and including \$n\$.

The advantage of this solution is that the set of powersOfTwo persists. This implies that we do not need to modify powersOfTwo if \$n\$ is smaller than any previous \$n\$. If \$n\$ is larger than all previous \$n\$ then powersOfTwo is already partially computed and we only need to extend it.

Building powersOfTwo has time complexity \$ O(log(N)) \$ where \$N\$ is the largest \$n\$ used. Looking up whether n in powersOfTwo has time complexity \$ O(1) \$ due to pythons guarantees about sets.

Some of the other answers here give good \$O(1)\$ solutions but lack an identifying feature of dynamic programs: (quote from wikipedia)

Once the solution to a given subproblem has been computed, it is stored or "memo­ized": the next time the same solution is needed, it is simply looked up.

Answer 5

All of the answers are good, but fail to address the dynamic programming nature of the solution. Quote from wikipedia:

Once the solution to a given subproblem has been computed, it is stored or "memo­ized": the next time the same solution is needed, it is simply looked up.

So we need to do some storing. And this storage needs to persist across multiple function calls...in this way the first few calls will be time consuming, but after that we're just doing lookups.

So the first change we make is to make the results dict a global...name it in all caps as per the python style guide.

RESULTS = {}  # initialize this separately, near the top of the program, outside of any functions or classes
def isPowerOfTwo(n):
    global RESULTS
    if n in RESULTS:
        return True

Then we also want to be breaking this problem down. In the iterative, bottom-up, approach, we start low and build upwards until we reach n, as you had. However, we start with a check to see if we have already completed this calculation. Also, I changed the first condition to if i == 1 because, technically, 1 is a power of 2.

    for i in range(1, n + 1):
        if i in RESULTS:
            continue  
        if i == 1:
            RESULTS[i] = True
        elif i % 2 != 0:
            RESULTS[i] = False
        else:
            RESULTS[i] = RESULTS[i/2]
    return RESULTS[n]

However, it bears mentioning that this problem -- determining if a number is a power of two -- isn't particularly well-suited to dynamic programming, and, as the other answers have shown, there are faster ways of determining if a number is a power of two.

Regardless, the full code is now:

RESULTS = {}  # initialize this separately, near the top of the program, outside of any functions or classes
def isPowerOfTwo(n):
    global RESULTS
    if n in RESULTS:
        return True
    for i in range(1, n + 1):
        if i in RESULTS:
            continue  
        if i == 1:
            RESULTS[i] = True
        elif i % 2 != 0:
            RESULTS[i] = False
        else:
            RESULTS[i] = RESULTS[i/2]
    return RESULTS[n]