8
\$\begingroup\$

I am trying to solve a problem to check whether a given number N is a power of k.

Example:

  • Input 9, 3 > True // 3**2 = 9
  • Input 10, 2 > False
  • Input 4096, 16 > True // 16**3 = 4096

I want to know if there is a better solution for this problem.

def check_Power(N,k):
    if N <= 0 or k <=0:
        print "not a valid input"
    else:
        for i in range (1,20):
            x = k**i
            if x == N :
                print " True "
                print k, "power ", i , "is", N
                break
            elif x> N:
                print "false"
                break

check_Power(244140625,5)
check_Power(4096, 16)
check_Power(0, 16)
check_Power(1,1)
\$\endgroup\$
  • 1
    \$\begingroup\$ For N to be a multiple of k it must be not less than k and must give an integer result when divided by k. If it is a power of k then the result of division must be either 1 of a multiple of k. So, you can just iterate dividing N by k as long as N is greater or equal k. Then, if it became 1, the initial value was a power of k, otherwise it wasn't. \$\endgroup\$ – CiaPan Jan 4 '18 at 10:18
  • \$\begingroup\$ One more note: test for k equal 1 — no number (except 1 itself) can be a power of 1... \$\endgroup\$ – CiaPan Jan 4 '18 at 10:20
  • \$\begingroup\$ Duplicate of codereview.stackexchange.com/questions/160924/… ? \$\endgroup\$ – dberm22 Jan 5 '18 at 13:57
15
\$\begingroup\$

Major

print " True "
  • Don't print but return variables from functions, that makes them usable later on
print "not a valid input"
  • You should raise an Exception with invalid input instead of printing it
for i in range (1,20):
  • This line will limit the input range from the function
if N <= 0 or k <=0:
  • Your guard clause does not cover all edge cases

Minor

  • Use better variable names, x doesn't say much
  • That else block is redundant, your if actually is a guard clause, remove the redundant indenting.
  • You have a few PEP8 issues

Revised code

def check_pow(N, k):
    if k < 0 or N < 0:
        raise ValueError("k and N must be greater than 0")
    if k == 0 and N == 1:
        return True
    if k in (0, 1) and N != 1:
        return False

    num = k
    while num < N:
        num *= k
    return num == N
\$\endgroup\$
  • 1
    \$\begingroup\$ Still not safe — verify check_pow (4, 1). \$\endgroup\$ – CiaPan Jan 4 '18 at 10:58
  • \$\begingroup\$ @CiaPan All edge cases are now accounted for \$\endgroup\$ – Ludisposed Jan 4 '18 at 12:27
  • 1
    \$\begingroup\$ Replace greater then with greater than \$\endgroup\$ – Olivier Grégoire Jan 4 '18 at 15:54
  • 2
    \$\begingroup\$ num isn't any more meaningful than x. \$\endgroup\$ – amalloy Jan 4 '18 at 19:27
  • 1
    \$\begingroup\$ Nothing. I think x was perfectly fine. But a more meaningful name would be something like product, or perhaps acc. \$\endgroup\$ – amalloy Jan 4 '18 at 22:03
18
\$\begingroup\$

I'd follow Ludisposed's answer.

Except, there's a simple way to do this. Use logarithms. Since the equation is \$N = k^a\$ you can change it to \$a = \log_k N\$. And so if \$a\$ is an integer, then you know that \$N\$ is a power of \$k\$.

import math

def check_power(N, k):
    return math.log(N, k).is_integer()

Since the above can error, and if there's an error it's definately not a power, then you can use:

def check_power(N, k):
    try:
        return math.log(N, k).is_integer()
    except Exception:
        return False

This has the some problems with floating point precision, so your can round the number to the closest integer, as you want to know if the \$a\$ is an integer. And so you can sub it back into the original equation to ensure that the numbers are right.

def check_power(N, k):
    return N == k**round(math.log(N, k))

Or if you're on Python 2:

def check_power(N, k):
    return N == k**int(round(math.log(N, k)))

This has a problem with some inputs, such as when \$N\$ and \$k\$ are \$0\$ or \$1\$. And so we can handle these special cases.

def check_power(N, k):
    if N == k:
        return True
    return N == k**round(math.log(N, k))

And so merging all the above, we can use the following:

def check_power(N, k):
    if N == k:
        return True
    try:
        return N == k**int(round(math.log(N, k)))
    except Exception:
        return False
\$\endgroup\$
  • \$\begingroup\$ You still need special cases for N == 0 or k in {0, 1}. \$\endgroup\$ – Veedrac Jan 4 '18 at 17:25
  • \$\begingroup\$ @Veedrac How do you mean? They raise exceptions, which are handled in the second code snippet above. \$\endgroup\$ – Peilonrayz Jan 4 '18 at 17:29
  • 2
    \$\begingroup\$ @Peilonrayz Ah, I was ignoring the earlier snippets since they're wrong, and just looking at the latter ones. Even in that case, check_power(1, 1) is wrong. \$\endgroup\$ – Veedrac Jan 4 '18 at 17:33
  • \$\begingroup\$ @Veedrac Maybe the easiest fix for this would be if N == k: return True. \$\endgroup\$ – Graipher Jan 5 '18 at 10:28
4
\$\begingroup\$

I recommend @Ludisposed's answer for the Pythonic comments.

The algorithm itself can be improved to get logarithmic complexity (ie, a logarithmic number of multiplies and comparisons).

The idea is to use:

  1. A galloping search to locate the two powers of 2 between which logk(N) would be if N was a power of 2.
  2. A binary search between the last smaller power of 2 and its successor to locate the exact exponent.

Visualizing it in code may be easier:

def check_pow(N, k):
    if k < 0 or N < 0:
        raise ValueError("k and N must be greater then 0")

    if k == 0 and N == 1:
        return True

    if k in (0, 1) and N != 1:
        return False

    powers = [1, k] #   powers[i] = k ** (2**i)

    #    Galloping search:
    #        With e = log-k(N),
    #        find a and b such that 2**a <= e < 2**b

    while powers[-1] < N:
        powers.append(powers[-1] * powers[-1])

    #    Binary search:
    #        Narrow down the gap to find the closest power of k
    #        that is <= to N.

    powers.pop()
    cursor = powers.pop()

    while len(powers) > 0:
        candidate = cursor * powers.pop()
        if candidate <= N:
            cursor = candidate

    return cursor == N

There are minor performance improvements possible still, short-circuitings notably, however they do not improve the worst-case complexity so I left them out to avoid mucking the algorithm.

\$\endgroup\$
4
\$\begingroup\$

This answer will focus on cleaning up the algorithm you used although, as other answers have shown, there are better algorithms for this problem. I will also answer how to loop over the infinite list of natural numbers with a generator. (Although I will refer to these as the counting numbers to clarify that I am not including 0.)

"Flat is better than nested"

An if statement that is checking a precondition for a function should avoid else because the else makes the entire function more deeply nested and adds little to the understandability when it is clear that the if statement is there to check if the provided arguments are valid.

Misc

I recommend returning True or False instead of printing so that you can reuse this function in later problems. As a slight benefit, returning a value also removes the need for break.

I also recommend using from __future__ import print_function so that you can be forwards compatible with Python3. Note that you will have to use parentheses with print and the new version below doesn't use print so this was left out of the code below.

Generators

Answering your question about how to loop over all the counting numbers, you could use a while loop or you could use generators. To show what your code might look like with a generator, see the following.

def counting_numbers():
    i = 1
    while True:
        yield i
        i += 1


def check_power(N, k):
    # Note that you could include 0 if you're careful about it.
    if N <= 0 or k <= 0:
        raise ValueError("N and k should be greater than 0")
    # We need to catch 1 as a special case because 1 ** n = 1 for all n
    # and thus 1 ** n will never be greater than N causing an infinite loop
    if k == 1:  # If the power is one
        return N == 1  # Then N is a power only if it is 1

    for i in counting_numbers():
        x = k ** i
        if x == N :
            return True
        elif x > N:
            return False

As you can see, you write what looks like a normal function and then use yield wherever you want to give a value to the for loop. The generator you are writing will yield control over to the loop whenever it hits a yield statement which is why this generator doesn't cause the program to seize up in an infinite loop. You can read more about generators in their original PEP 255 or in various online tutorials. Just know that they will stop upon hitting the end of their block like a function would or a return statement. (Sidenote: don't try using return x in a generator, this is related to sending a StopIteration and doesn't make the generator return a value like you might expect.)

In this case, we actually don't have to write counting_numbers because itertools already has this builtin as itertools.count but because we want to start from 1 instead of 0 we will have to call count(1) instead of count() which would start from 0. We can now rewrite the above solution to

from itertools import count


def check_power(N, k):
    if N <= 0 or k <= 0:
        raise ValueError("N and k should be greater than 0")
    # This special case is to avoid an infinite loop
    if k == 1:
        return N == 1

    for i in count(1):
        x = k ** i
        if x == N :
            return True
        elif x > N:
            return False
\$\endgroup\$
0
\$\begingroup\$

This can be done without looping. The idea is to rearrange $$N=k^c$$ to $$c = \log_k N = \frac{\log N}{\log k}.$$ If the exponent is an integer, then it is a perfect power. In the below code, some extra work is done to avoid floating-point rounding errors.

import math

def check_Power(N,k):
    # input validation
    if N < 0:
        raise Exception('N must be non-negative')
    if k < 0:
        raise Exception('k must be non-negative')

    # 1 to any power can only equal 1
    if k == 1:
        return N == 1

    # Only raising 0 to a non-zero power results in zero
    if N == 0 or k == 0:
        return k == N

    # Use math.floor to make the exponent an integer
    # that is within 1 of the actual answer
    exponent = math.floor(math.log(N)/math.log(k))

    # Test whether the integer exponent solves
    # the problem and adjust the exponent as needed
    testN = k**exponent
    if testN < N:
        exponent += 1
    elif testN > N:
        exponent -= 1
    else:
        return True # testN == N

    return k**exponent == N # check adjusted exponent
\$\endgroup\$
0
\$\begingroup\$

I'm going to assume you mean integers since that's what your test data suggests. I'm also assuming the powers are non-negative integers so as not to involve roots (a).

In that case, there's no need to do all those power calculations, you just need to realise that, if n is a power of k, then continuously multiplying an accumulator (initially k) by k will either:

  • reach n exactly (if it's a power).
  • exceed n (if it's not a power).
  • never satisfy either of those conditions because the accumulator never gets any closer to n (see below code for those conditions).

In any case, the code you have only checks if n is a power of k with an exponent less than or equal to twenty, it won't return true for k = 2, n = 2**31 for example.

The code to do it a a less limited way is a stunningly simple:

def isPower(n, k):
    # Special cases.

    if k == 0:   return n == 0       # 0^not-0 always 0, 0^0 undefined
    if k == 1:   return n == 1       # 1^n always 1
    if k == -1:  return abs(n) == 1  # -1^n alternates +/-1

    # abs(k) is now >= 2 so it will always increase in magnitude.
    acc = k
    while abs(acc) < abs(n):
         acc = acc * k
    return acc == n

(a) If you decide to use floating point values, it gets a little more complicated. You then have to cater for more possibilities:

  • if the power is allowed to be fractional, you'll have to cater for roots as well as powers;
  • where k is be between -1 and 1, it will always approach zero rather than getting larger, so you'll need to adapt for that;
  • the adaptation for that must also take into account whether n is in that range or whether its absolute value is greater than or equal to one;

There's may well be other issues that haven't sprung immediately to mind, I won't think too much about them as, in the absence of further information, they're probably unnecessary.

\$\endgroup\$
  • \$\begingroup\$ Isn't that essentially the solution suggested in this answer codereview.stackexchange.com/a/184266/35991 ? \$\endgroup\$ – Martin R Jan 5 '18 at 6:11
  • \$\begingroup\$ The fact that the five lines of calculation loop is pretty much the same does not, I believe make the answer as a whole identical. There is no reason to limit the input variables to positive integers, my answer allows for either sign. It also details what would be needed to make it work for non-integers as well. \$\endgroup\$ – user7649 Jan 5 '18 at 6:39
  • \$\begingroup\$ For which negative input? Your isPower(-8, -2) returns False. \$\endgroup\$ – Martin R Jan 5 '18 at 7:03
  • \$\begingroup\$ @MartinR, good catch, I believe I've fixed that now, it was a slight bug in the terminating condition for the loop. \$\endgroup\$ – user7649 Jan 5 '18 at 7:10
  • \$\begingroup\$ Your isPower(1, -1) returns False. \$\endgroup\$ – Martin R Jan 5 '18 at 7:55

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.