Solution to Chocolates-By-Numbers by codility

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

   Reply

   • You are right! Thanks for your reminder!

     Reply

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!

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   def solution(N,M):       # We start eating the first candy     start_eating = 0     count = 0       while True:         # we eat the follwing candies.         # Remember we ate one already         count += 1 + ( (N - start_eating - 1) // M)         # Some are left at the end         left_candies = (N - start_eating - 1) % M         # In the next iteration we start eating at a different place         start_eating = M - left_candies - 1         # if we are back at candy 0 means we are done         if start_eating == 0:             break       return count

   Reply

3. A java solution with 100/100

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   class Solution {       public int solution(int N, int M) {         // write your code in Java SE 8           int oneRoundMaxChocolate =N/M+1;         int num =0;         int round =1;         while(  round<= (N/oneRoundMaxChocolate) +1 ){             if( ((round*(long)N))%M==0)                 return (int)(((round*(long)N))/M);             else round++;         }         return N;     } }

   Reply

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"

   Reply

5. c# 100%

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   public int solution(int N, int M)         {             // find lcm (a num that divided by N and by M), ex N=10, M=4: lcm =20 => 20 / 10 = 2 and 20 / 4 = 5;             var lcm = (long)N * M / gcd(N, M);               // calculate how many times lcm contains M - how many turns required to revisit same index             var turns = (int)(lcm / M);               return turns;         }           private int gcd(int N, int M)         {             int a = N;             int b = M;               // not recurcive version of gcd             while( a % b != 0)             {                 var tmpValue = a;                   a = b;                 b = tmpValue % b;             }               return b;         }

   Reply