14
\$\begingroup\$

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?

\$\endgroup\$
  • 6
    \$\begingroup\$ One style note: in Python, function names are snake_case rather than camelCase. See PEP 8, the Python style guide. \$\endgroup\$ – alexwlchan Jul 19 '15 at 20:18
  • \$\begingroup\$ @alexwlchan Thanks for the advice and link. Didn't know that. \$\endgroup\$ – sschmeck Jul 19 '15 at 20:35
12
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
10
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks. I guess I asked the wrong question. Your solution is very efficient but my example's intention is showing the principle of Dynamic Programming with Bottom-up approach. How can I improve my question? \$\endgroup\$ – sschmeck Jul 19 '15 at 20:43
  • 2
    \$\begingroup\$ Here is more info on very efficient ways to do this with bit fiddling tricks. \$\endgroup\$ – jacwah Jul 19 '15 at 20:45
  • 4
    \$\begingroup\$ Having to convert the number to a "binary string" and then call a method for searching the entire string for a "1" is not very efficient. I recommend just returning n == (n & -n). Read why this works here. \$\endgroup\$ – SirPython Jul 19 '15 at 20:53
  • 5
    \$\begingroup\$ @SirPython - that's a clever implementation of the algorithm. Nice find - it saves having to convert to a String at all, which is a good thing. sschmeck - about the problem itself - perhaps the point is that this power-of-two problem is a poor candidate as a tool for using to teach dynamic programming - consider something else, which makes sense. \$\endgroup\$ – rolfl Jul 19 '15 at 20:59
4
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks. It's very concise. But my example above may not use recursion/memoization. \$\endgroup\$ – sschmeck Jul 19 '15 at 20:31
  • 1
    \$\begingroup\$ If the size of n was big enough, couldn't this result in a stack overflow? \$\endgroup\$ – SirPython Jul 19 '15 at 21:07
  • \$\begingroup\$ @SirPython Sure, n must be 2**1001 to Overflow the Stack, high but possible. Python does not optimize tail call. \$\endgroup\$ – Caridorc Jul 19 '15 at 21:10
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.