Short Problem Definition:
There are N chocolates in a circle. Count the number of chocolates you will eat.
Link
Complexity:
expected worst-case time complexity is O(log(N+M))
expected worst-case space complexity is O(1)
Execution:
N and M meet at their least common multiply. Dividing this LCM by M gets the number of steps(chocolates) that can be eaten.
Solution:
def gcd(p, q):
if q == 0:
return p
return gcd(q, p % q)
def lcm(p,q):
return p * (q / gcd(p,q))
def solution(N, M):
return lcm(N,M)/M
def naive(N,M):
eaten = [False] * N
at = 0
cnt = 0
while eaten[at] != True:
eaten[at] = True
at = (at + M) % N
cnt += 1
return cnt