Codility 'ChocolatesByNumbers' Solution

Martin Kysel · August 10, 2014

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

Twitter, Facebook