检查数字N是否为K的幂

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)

#1 楼

您可能已经使用了这样一个事实：如果\ $ n = k ^ x \ $，则\ $ \ log_k（n）= x \ $是整数。但是，由于Python中float的精度有限，这会产生一些问题。为了解决这个问题，我们可以同时测试对数ceil和floor，看看是否可以取回n。这样，我们最多只需要进行三个昂贵的计算。

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

现在，无需进行两次幂运算，我们可以意识到k ** int(ceil(kth_log)) = k * k ** int(floor(kth_log))的速度很小-在大约50％的情况下提高效率（由于@KyleGullion：

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

这似乎适用于相当大的值（我检查了大约\ $ 2 ^ {32000 }，2 ^ {20000}-1，3 ^ {20000} \ $）。这是下表中的时间表。

要获得更多的速度提升，您可以窃取@pantarei的答案是个不错的过早退出方法，如果数字是k的幂，这会牺牲一些速度，但如果不是x % 1 == 0的话，则会获得约2的系数：

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

最后是一些时间，它比较了我的代码和@ user1825464的答案，@ pantarei的答案，@ RyanMill的答案，@ Eevee的答案和@JamesMishra的答案的代码：

+-------------+---+----------+-------------+-----------+------------+---------+--------------+
|      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      |
+-------------+---+----------+-------------+-----------+------------+---------+--------------+

因此，日志并不关心它是否实际上是k次方，而循环在这种情况下必须做更多的工作，但可能会发现它的性能不是更快。


您可以使用!= 0来检查整数，否则使用float来检查整数（感谢@Peilonrayz在注释中）：

from math import log

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

但是，正如注释中所述，这仅在log的精度不再足以区分n的结果之前有效不是整数。

对于形式为\ $ 2 ^ x-1 \ $的数字，如@GarethReese所述，这发生在\ $ x = 48 \ $，所以您应该问如果k和q4312079q有任何限制。

#2 楼

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)

其复杂度为\ $ O（log（log（N））\ $，相比之下，\ $ O（log（N））\ $为简单除法或对数。

这背后的原因是，如果\ $ N \ $是\ $ K \ $的幂，则它在基数\ $ K \ $中的表示类似于\ $ 000100 ..00 \ $。通过检查形式为\ $ K ^ {2 ^ i} \ $的\ $ N \ $的最大除数，进行二进制搜索来查找该位置（如果存在），进行除法，然后执行递归地返回，直到它不除（不是\ $ K \ $的幂），或者返回1（并且是\ $ K \ $的幂）。

#3 楼

有点大胆的猜测，但也许他们正在寻找使用divmod的原因，因为具有相同操作数的%和/本质上是相同的操作？

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

    return n == 1

#4 楼

这是@Graipher答案的一个版本，但是它更多地依赖于Python int的属性。

 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
 

如果test_pow遇到浮点问题，则test_n_floor和test_n_ceil都不等于n。这是因为两个int上的Python指数运算符将产生int或long类型，并且不会丢失精度。

>>> 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

贷方@Graphier在我的原始答案中发现了一个错误。我已经更新了修复程序。

#5 楼

为什么不直接使用它呢？

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)

此代码更易于理解，并且使用了更有效的操作。

但是@Graipher的答案可能是最有效的方法。

#6 楼

二进制搜索

他们对复杂性感兴趣。我很确定他们希望您使用二进制搜索。

这是一个面试问题。因此，您必须展示自己对算法和复杂性的了解。

仅通过重复乘法（或除法）进行幂运算就不会削减它。
仅使用math.log，这可能是您在实践中将如何做，也不会了解您的知识。

要进行二进制搜索，首先需要一种快速的方法来获得一个上限。然后通过移动上限（hi）和下限（lo），以标准教科书方式实现二进制搜索。

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

子例程和整体函数每个以\ $ \ mathcal {O}（log（e））\ $。运行，其中e是从n到以k为底的对数。但是，基本运算是取幂，它本身位于\ $ \ mathcal {O}（log（e））\ $中。因此，总体复杂度为\ $ \ mathcal {O}（log（e）^ 2）\ $。

#7 楼

如果n == 0或k == 1，则代码的复杂性非常非常糟糕，因为循环没有完成:-(因此应该解决。

当人们讨论复杂性时，最糟糕的是案例和平均案例在计算机科学中，人们通常主要关注最坏的情况。在现实生活中，平均案例更为重要。

在您的案例中，最坏的情况是n = k ^ m ，则需要m步，但是，如果随机选择n，则仅一步就停止的（k-1）/ k几率是两步，（k-1）/ k ^ 2 （k-1）/ k ^ 3三个步骤，依此类推。即使对于k = 2，平均步骤数也只有两个。

当然，这只是我说您的代码还可以。在求职面试中，您可能必须与面试官说的一切相处。