I can do it in only O(k) time can someone be that kind to help me. I can not use build in functions.

def potnr(a, b):
    rez = 1
    while b>0:
        if b%2:
            rez = rez * a

        b = b // 2
        a = a * a
        
    return rez

def liczba(n, m):
    k = 1
    while potnr(n, k) < m:
        k  = 1

    return k

print(liczba(2, 16))

I can do it in only O(k) time can someone be that kind to help me

CodePudding user response：

n^k >= m if and only if k >= log m base n

Since log m base n = log m / log n, this is as simple as:

from math import log, ceil
def smallest_k(n, m):
    return ceil(log(m)/log(n))

This runs in O(1) time.

CodePudding user response：

This one should work:

import math
def min_power(n,m):
    b=1
    while n**b < m:
        b *= 2
    a = b/2
    while b-a > 1:
        c = (a b)/2
        if n**c < m:
            a = c
        else:
            b = c
    return math.ceil(b)

min_power(35,10**250)
# Out[23]: 162

CodePudding user response：

First determine any natural number k for which n ^ k >= m. Then refine your estimate to find the smallest such k.

It's easiest to find the initial estimate for k as a power of 2. Have a temporary value which holds n ^ k. Start from k = 1, repeatedly multiply k by 2, and square your temporary variable, until your k is sufficiently big.

Your real k will be greater than half the estimate you found. Numbers in that range have log2(k) bits. Check each bit, starting from the most significant one. For each such bit, calculate n ^ k for two values of k: with that bit equal to 0 and 1. Compare with m - this will tell you the value of that bit. Proceed to lower-significant bits, until you get to bit 0 (least significant bit).

I am not sure you are allowed to assume that calculating n ^ k has O(1) complexity. If not, you have to store intermediate results for all n ^ k calculations at first stage, or alternatively, use sqrt to calculate lesser powers of n.