Solution to Chocolates-By-Numbers by codility

17 Feb

Question: https://codility.com/demo/take-sample-test/chocolates_by_numbers

Question Name: Chocolates-By-Numbers or ChocolatesByNumbers

When we met with an empty wrapper, we must have been this position for twice. We use i for the first time and j for the second time. Due to the modulo feature, there must be nature number, to say k, so that: i * M + k * N = j * M. Then we could easily prove that the smallest (earliest) i must be zero (for all i != 0, then (i-i) * M + k * N = (j-i) * M ). So the first eaten position would be first position that you meet again. Finally, the j would be the number of chocolates that you will eat.

6 Replies to “Solution to Chocolates-By-Numbers by codility

  1. You can just remove M from last two lines, so it becomes:
    N / gcd(N, M) # this is the correct result

  2. First of all, congratulations for the blog, it is an incredible source of knowledge!

    I came up with an alternative solution without using the gcd() function. It looks good but the performance for extremely large numbers not satisfied, I just can’t figure out why https://app.codility.com/demo/results/trainingXCB2M3-MYJ/
    I leave it here in case someone finds it useful, its only 87%. Thanks again!

  3. A java solution with 100/100

  4. @Leo,

    How did you come up with the following?

    round <= (N/oneRoundMaxChocolate) +1

    The above implies that the maximum value of "round" is "(N/oneRoundMaxChocolate)+1"

  5. c# 100%

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!