20
\$\begingroup\$

I was asked this question in interview:

Check if a number N is a power of K.

Example: N = 32, K = 2 => True

N = 40, K = 5 => False

I wrote following code but got the feedback that, complexity could have be improved, How to improve its complexity?

def check_kth_power(n, k):
        while n%k == 0:
            n = n/k

        if n != 1:
            return False
        return True


print check_kth_power(128, 5)
\$\endgroup\$
  • 3
    \$\begingroup\$ You know N = 40, K = 5 is false as every power if 5 is odd. And every power of an even is even. \$\endgroup\$ – paparazzo Apr 16 '17 at 20:23
  • 3
    \$\begingroup\$ The name "check_kth_power" seems to ask whether there is some x for which n = x^k. I would suggest check_power_of_k as a better name. \$\endgroup\$ – wnoise Apr 17 '17 at 23:07
17
\$\begingroup\$

You could have used the fact that if \$n = k^x\$, then \$\log_k(n) = x\$ is an integer. However, due to the limited precision of floats in Python, this will generate some problems. To get around this, we can test both the ceil and the floor of the logarithm to see if we can get back n. This way we only ever need to do three expensive computations at most.

from math import log, ceil, floor

def check_kth_power(n, k):
    kth_log = log(n, k)
    return k ** int(ceil(kth_log)) == n or \
           k ** int(floor(kth_log)) == n

Now, instead of doing the exponentiation twice, we can realize that k ** int(ceil(kth_log)) = k * k ** int(floor(kth_log)) for a small speed-boost in about 50% of the cases (thanks to @KyleGullion:

def check_kth_power(n, k):
    candidate = k ** int(log(n, k))
    return candidate == n or k * candidate == n

This seems to work for quite large values (I checked up to about \$2^{32000}, 2^{20000} - 1, 3^{20000}\$). This is the version in the timing table below.

To get even more of a speed-boost, you can steal the nice premature exit from @pantarei's answer. This sacrifices some speed in the case that the number is a power of k, but gains about a factor 2 if it is not:

def check_kth_power_gp(n, k):
    if n%k != 0:
        return False
    candidate = k ** int(log(n, k))
    return candidate == n or k * candidate == n

And, finally, some timings. This compares my code and the code from @user1825464's answer, @pantarei's answer, @RyanMill's answer, @Eevee's answer and @JamesMishra's answer:

+-------------+---+----------+-------------+-----------+------------+---------+--------------+
|      n      | k | Graipher | user1825464 | panta rei | Ryan Mills |  Eevee  | James Mishra |
+-------------+---+----------+-------------+-----------+------------+---------+--------------+
| 2**1000     | 2 | 1.73 µs  | 9.9 µs      | 105 µs    | 12.9 µs    | 388 µs  | 3.23 µs      |
| 2**1000 - 1 | 2 | 1.99 µs  | 2.5 µs      | 619 ns    | 15.7 µs    | 765 ns  | 3.09 µs      |
| 3**1000     | 2 | 2.41 µs  | 4.26 µs     | 854 ns    | 22.4 µs    | 1.04 µs | 4.08 µs      |
| 3**1000     | 3 | 2.81 µs  | 12.6 µs     | 125 µs    | 13.8 µs    | 556 µs  | 4.51 µs      |
+-------------+---+----------+-------------+-----------+------------+---------+--------------+

So the log does not care if it actually is a kth power, whereas the loop has to do more work in that case, but potentially finds that it is not a power faster.


You could be checking for integerness using x % 1 == 0 for integers, != 0 otherwise (thanks to @Peilonrayz in the comments):

from math import log

def check_kth_power(n, k):
    return log(n, k) % 1 == 0

But, as noted in the comments, this works only until the precision of float is not enough anymore to distinguish that the result of the log is not an integer.

For numbers of the form \$ 2^x - 1\$, this happens at \$x = 48\$, as noted by @GarethReese, so you should have asked if there are any limits on n and k.

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Jamal Apr 17 '17 at 9:34
  • \$\begingroup\$ You can save a lot of work by using modulo exponentiation to check divisibility. ie return pow(k, int(ceil(kth_log)), n) == 0 or pow(k, int(floor(kth_log)), n) == 0 \$\endgroup\$ – Kyle Gullion Apr 17 '17 at 16:50
  • 1
    \$\begingroup\$ @KyleGullion Are you sure? For 2**50 and 2**50-1, your version is ~50% slower. \$\endgroup\$ – kyrill Apr 17 '17 at 23:53
  • 1
    \$\begingroup\$ How about test case n=16, k=-2? I'm betting that a lot of the answers break. \$\endgroup\$ – Peter Taylor Apr 19 '17 at 9:51
  • 2
    \$\begingroup\$ True is correct: 16 == (-2)^4. Other interesting test cases would be n=8, k=-2 for which the correct answer is False and n=-8,k=-2 for which the correct answer is True. \$\endgroup\$ – Peter Taylor Apr 19 '17 at 11:12
17
\$\begingroup\$
def check_kth_power(n, k):
    if n == 1:
        return True

    div = k
    while div * div <= n:
        div = div * div

    if n % div != 0:
        return False
    return check_kth_power(n / div, k)

The complexity of this is \$O(log(log(N))\$, compared to \$ O(log(N)) \$ for straightforward division or logarithms.

The reasoning behind this is that if \$ N \$ is a power of \$ K \$, its representation in base \$K\$ looks something like like \$000100 ..00\$. We can do something like a binary search to find the position of this one (if it exists) by checking the largest divisor of \$N\$ of the form \$ K^{2^i} \$, dividing it out, then doing this recursively until it either doesn't divide out (and isn't a power of \$K\$), or it returns 1 (and is a power of \$K\$).

\$\endgroup\$
  • \$\begingroup\$ I really thought I could get this into the recursion limit, but it works for surprisingly big numbers. Have a look at the timings I took on my machine for a comparison of yours and my (fixed) algorithm in my updated answer. \$\endgroup\$ – Graipher Apr 17 '17 at 9:02
  • \$\begingroup\$ @Graipher How about tail-call optimization? Could it be that Python optimizes the call into "jump"? \$\endgroup\$ – kyrill Apr 17 '17 at 15:55
  • 3
    \$\begingroup\$ @kyrill Python doesn't do tail call optimization and probably never will. See stackoverflow.com/questions/13591970/… \$\endgroup\$ – Graipher Apr 17 '17 at 19:05
  • \$\begingroup\$ @Graipher Thanks, that's some interesting reading. \$\endgroup\$ – kyrill Apr 17 '17 at 19:20
  • 1
    \$\begingroup\$ Transforming the tail call to an iteration is not hard to do by hand, of course. \$\endgroup\$ – wnoise Apr 17 '17 at 23:02
11
\$\begingroup\$

Bit of a wild guess, but perhaps they were looking for you to use divmod, since % and / with the same operands are essentially the same operation?

def check_kth_power(n, k):
    while True:
        q, r = divmod(n, k)
        if r == 0:
            n = q
        else:
            break

    return n == 1
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to Code Review! Nice to see a high ranked SO user come over here. :) \$\endgroup\$ – Peilonrayz Apr 17 '17 at 13:38
  • 1
    \$\begingroup\$ i was just passing through since this caught my eye in the sidebar, but now i feel somewhat obliged to hang around, argh :) \$\endgroup\$ – Eevee Apr 18 '17 at 7:42
  • \$\begingroup\$ I added your function to the timing table, the spread for values which are a kth power and which are not is even larger for this variant. Quite interesting to see. \$\endgroup\$ – Graipher Apr 18 '17 at 10:06
  • \$\begingroup\$ ha, looks like function call overhead dwarfs what little you save from not dividing twice \$\endgroup\$ – Eevee Apr 18 '17 at 11:31
9
\$\begingroup\$

This is a version of @Graipher's answer, but it relies more on properties of Python ints.

from math import log
def check_kth_power(n, k):
    test_pow = int(log(n, k))
    test_n_floor = k ** test_pow
    test_n_ceil = k ** (test_pow + 1)
    return n == test_n_floor or n == test_n_ceil

If test_pow suffers from floating point issues, then neither test_n_floor nor test_n_ceil will equal n. This is because the Python exponent operator on two ints will produce either an int or long type, and will not lose precision.

>>> log(2 ** 50, 2)
50.0
>>> log(2 ** 50 - 1, 2)
50.0
>>> check_kth_power(2 ** 50, 2)
True
>>> check_kth_power(2 ** 50 - 1, 2)
False
>>> 2 ** 50 - 1 == 2 ** int(log(2 ** 50-1, 2))
False
>>> check_kth_power(3 ** 5, 3)
True
>>> check_kth_power(3 ** 5 + 1, 3)
False
>>> check_kth_power(3 ** 5 - 1, 3)

False

Credit goes to @Graphier for discovering a bug in my original answer. I have updated with a fix.

\$\endgroup\$
  • 3
    \$\begingroup\$ You can actually avoid an exponentiation here by noting that test_n_ceil == k*test_n_floor. \$\endgroup\$ – Kyle Gullion Apr 18 '17 at 2:58
  • \$\begingroup\$ @KyleGullion That's a good suggestion, implemented it in my answer. It gives a speed-boost of from about 0.9 to 2, so it's worth it :) \$\endgroup\$ – Graipher Apr 18 '17 at 11:54
  • \$\begingroup\$ Added you to the timing table (even though it becomes horizontally scrolling now). My code is faster (and was already without the optimization by Kyle), because I only calculate the second exponentiation if the first one is not equal to n, thus saving the computation if the number is a power of k in 50% of the cases (50% because sometimes the floating point accuracy results in it being slightly above or below the integer value). \$\endgroup\$ – Graipher Apr 18 '17 at 12:00
6
\$\begingroup\$

Why not doing it the (straight) forward way?

def check_kth_power(n, k):
    if n%k != 0:
        return False

    pow = k
    while pow < n:
        pow = pow * k
    return pow == n

print check_kth_power(128, 5)

This code is easier to understand, and uses more efficient operations.

But @Graipher's answer is probably the most efficient way to do it.

\$\endgroup\$
  • \$\begingroup\$ See the timings in my answer. Your code is killing it if the number is not a kth power, but loosing if it is :) \$\endgroup\$ – Graipher Apr 17 '17 at 9:31
  • \$\begingroup\$ @Graipher So you can add that little check n%k != 0 into your code as well and you'll be killing it too... \$\endgroup\$ – kyrill Apr 17 '17 at 15:57
  • \$\begingroup\$ @kyrill I tried it, the case where it is a power of k goes from ~2us to ~3us, while if it is not, it goes down to <1us. So it depends on if most numbers you test are a power or not... \$\endgroup\$ – Graipher Apr 18 '17 at 15:44
6
\$\begingroup\$

Binary search

They're interested in complexity. I'm pretty sure they wanted you to use binary search.

This is an interview question. So you have to show what you know about algorithms and complexity.

  • Just doing exponentiation by repeated multiplication (or division) doesn't cut it.

  • Just using math.log, which is probably how you would do it in practice, also won't get your knowledge across.

To do binary search, first you need a fast way to get an upper bound. Then implement binary search in the standard textbook way, by shifting the upper (hi) and lower (lo) bounds.

def got_the_power(n, k):
    '''
    Returns True if n is a power of k, otherwise returns False.    
    '''

    def get_upper_bound(n, k):
        '''
        Finds an upper bound for e where k**e = n.
        '''
        a, e = k**2, 2
        while a < n:
            a *= a
            e = e*2
              # The above line was e = e**2 in the original post.
              # Bug spotted by Graipher. Thanks! 
        return e

    hi = get_upper_bound(n, k)
    lo = 0
    while hi - lo > 1:    # standard binary search
        m = (hi - lo) / 2 + lo
        a = k**m
        if a == n:
            return True
        if a > n:
            hi = m
        else:
            lo = m
    return False

# Test it out
print got_the_power(64, 2)  # True
print got_the_power(63, 2)  # False

Both the upper bound subroutine and the overall function each run in \$\mathcal{O}(log(e))\$., where e is the log of n to base k. However, the fundamental operation is exponentiation, which is itself in \$\mathcal{O}(log(e))\$. So the overall complexity is \$\mathcal{O}(log(e)^2)\$.

\$\endgroup\$
  • \$\begingroup\$ This seems overcomplicated and inefficient because it discards so many intermediate values which it then uses again. It would make much more sense to build a list of k^(2^i) until you get a value which exceeds n (effectively get_upper_bound but storing intermediate values) and then work backwards down the list applying the logic that if the list element is greater than the accumulator then it can be discarded, but otherwise it must divide it exactly to give the next accumulator. \$\endgroup\$ – Peter Taylor Apr 19 '17 at 9:48
  • \$\begingroup\$ True, storing the intermediate values would definitely shave off a constant factor. But it won't change the time complexity. And I wouldn't be able to present a textbook binary search as part of the code. \$\endgroup\$ – Ryan Mills Apr 20 '17 at 12:39
5
\$\begingroup\$

Complexity of your code is very, very bad if n == 0 or k == 1 because your loop doesn't finish :-( So that should be fixed.

When people discuss complexity, there's worst case and average case. In computer science, people often look primarily at the worst case. In real life the average case is more important.

In your case, the worst case is that n = k^m, in which case it takes m steps. However, if n is chosen at random, then the chances are (k-1) / k that you stop after just one step, (k-1) / k^2 for two steps, (k-1) / k^3 for three steps and so on. Even for k = 2, the average number of steps is just two.

Of course that's just me saying that your code is Ok. In a job interview, you may have to live with whatever the interviewer says.

\$\endgroup\$
  • \$\begingroup\$ Or if k == 0. Not to mention k < 0, which breaks most of the answers. \$\endgroup\$ – Peter Taylor Apr 19 '17 at 9:50

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.