Short Problem Definition:
There are N chocolates in a circle. Count the number of chocolates you will eat.
expected worst-case time complexity is O(log(N+M));
expected worst-case space complexity is O(1)
N and M meet at their least common multiply. Dividing this LCM by M gets the number of steps(chocolates) that can be eaten.
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
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.