Lesson 10: ChocolatesByNumbers (Chocolates by Numbers)

Lesson 10:  ChocolatesByNumbers
https://codility.com/programmers/lessons/10

This is a easy problem. 

We have to stop eating more chocolates when we reached the same location we visited before. So the answer will be 'the least common multiple of N and M(LCM) / M'. As LCM can be computed by (N * M) / gcd(N,M), LCM / M = (N * M) / gcd(N, M) / M = N / gcd(N, M).

If someone feel the above is unclear imagine such a situation below.

location (N = 7): 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0
position (M = 4): X       X       X       X       X       X       X       X

As above, we reach the same location at the LCM of N and M.


This gives the 100% score.

//we expect the compiler will perform the tail call optimazation.
int gcd(int a, int b, int res)
{
    if (a == b){
        return res * a;
    }
    if (a % 2 == 0 && b % 2 == 0){
        return gcd(a >> 1, b >> 1, 2 * res);
    }
    if (a % 2 == 0){
        return gcd(a >> 1, b, res);
    }
    if (b % 2 == 0){
        return gcd(a, b >> 1, res);
    }
    if (a > b){
        return gcd(a - b, b, res);
    }
    
    return gcd(a, b - a, res);    
}
int solution(int N, int M) 
{
    int denominator   = gcd(N, M, 1);
    int numerator     = N;
    
    return (numerator / denominator);
}