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

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.