Problem

Two positive integers N and M are given. Integer N represents the number of chocolates arranged in a circle, numbered from 0 to N - 1. 

You start to eat the chocolates. After eating a chocolate you leave only a wrapper.

You begin with eating chocolate number 0. Then you omit the next M - 1 chocolates or wrappers on the circle, and eat the following one. 

More precisely, if you ate chocolate number X, then you will next eat the chocolate with number (X + M) modulo N (remainder of division).

You stop eating when you encounter an empty wrapper. 

For example, given integers N = 10 and M = 4. You will eat the following chocolates: 0, 4, 8, 2, 6.

The goal is to count the number of chocolates that you will eat, following the above rules. 

Write a function:

    int solution(int N, int M); 

that, given two positive integers N and M, returns the number of chocolates that you will eat.

For example, given integers N = 10 and M = 4, the function should return 5, as explained above. 

Write an efficient algorithm for the following assumptions:

·         N and M are integers within the range [1..1,000,000,000].

Note:

Why do you stop eating, when you encounter an empty wrapper? – Because adding M repeatedly will simply meet other empty wrappers. 

You can only stop eating after you have completed at least one cycle.

The lesson (tutorial) for this problem is on greatest common divisor (HCF) and least common multiple (LCM). So the reader should expect that the solution to the problem needs either HCF or LCM or both, with fast algorithms. 

With the given data, the LCM of 10 and 4 is 20. Now, 20 / 4 = 5, the number eaten. If normal counting was involved (instead of modulo counting), the last eating position would have been 16 (ordinal number), and the first wrapper met would have been at position 20 (ordinal number).

When you eat chocolate 0, you count 4 chocolates beginning from chocolate 1, and you are at chocolate 4 (zero based indexing). You eat chocolate 4. Those are two chocolates eaten. Next you count 4 chocolates beginning from chocolate 5. You eat chocolate 8. Those are three chocolates eaten. Next you count 4 chocolates beginning from chocolate 9. You eat chocolate 2, not chocolate 12, since there are 10 chocolates, indexed from 0 to 9, and using modulo counting. Those are four chocolates eaten. Next you count 4 chocolates beginning from chocolate 3. You eat chocolate 6, not chocolate 16, since there are 10 chocolates, indexed from 0 to 9. Those are five chocolates eaten. Next you count 4 chocolates beginning from chocolate 7. You arrive at chocolate 0. You are to eat chocolate 0 again (not possible). Chocolate 0 had already been eaten. There you stop. 

So, out of 20 chocolates (zero based indexed from 0 to 19), you have eaten 20 ÷ 4 = 5 chocolates.

Determining the LCM of 10 and 4 from first principles is as follows: 

Multiples of 10 and 4 are:

    10: 10, 20, 30, 40, 50, 60, etc.

     4: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, etc.

As 4 is being added onto itself and 10 also being added onto itself, the first number at which the additions meet, is 20, which is the LCM. 

Common multiples of 10 and 4 are:

    20, 40, 60, etc. (keep adding 20) 

The least of these common multiples is:

    20 

You eat chocolate number 0. Plus 4 and you eat chocolate number 4; two chocolates eaten. Plus 4 and you eat chocolate number 8; three chocolates eaten. Plus 4 and you eat chocolate number 12, bypassing chocolate number 10 (in non-modulus counting); four chocolates eaten. Plus 4 and you eat chocolate number 16 (in non-modulus counting); five chocolates eaten. Plus 4 and you should eat chocolate number 20 (assuming it was still there), and addition of 10 onto itself meets the repeated adding of 4 onto itself, at 20 (in non-modulus counting); still five chocolates eaten.

Going in a cycle (circle), position 20 is the same as position 0. Twenty is the LCM of 10 and 4. Twenty divided by 4 gives 5, the answer. 

The formula is:

where N is the original number of chocolates in the circle, and M is the interval.

Strategy

- Have a function that determines the greatest common divisor (HCF) with a fast algorithm.

- Have another function that uses the GCD (as denominator) to determine the LCM (with product of given numbers, as numerator).

- The solution() function applies the formula directly.

Smart Solution

A solution() function and necessary code, is in the following program (read the code and comments): 

#include <iostream> 
using namespace std;

long int gcd(long int a,  long int b) {
    if (a%b==0) return b;
    return gcd(b,a%b);
}
long int lcm(long int a, long int b) {
    return (a*b)/gcd(a,b);
}

int solution(int N, int M) {
    return lcm(N,M)/M;
}

int main(int argc, char **argv) 
{ 
    int ret = solution(10, 4);

    cout << ret << endl;

    return 0; 
}

The output is: 

    5

At app.codility.com/programmers the scoring and detected time complexity for this solution() is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(log(N + M))

Thanks for reading.