ChocolatesByNumbers- Find the number of N chocolates in a circle

Question

Recently, i have been indulging in a lot of codility challenges to improve my coding performance. For each of this exercise, I always aim for simple solutions as opposed to complicated ones that arrive at the same answer . The question is

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:

class Solution { public 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.

Assume that:

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

expected worst-case time complexity is O(log(N+M)); expected worst-case space complexity is O(log(N+M))

I am aware a similar questions has been asked in java ChocolatesByNumbers but my question is more directed to C#

public static int PrintNChocolatesInaCircle(int N, int M)
{
    int counter = 1;
    int start = 0;
    int value;
    while ((start + M) % N != 0)
    {
        value = (start + M) % N;
        start = value;
        counter++;
    }
    return counter;
}

Codility scored my code in terms of Correctness 100% but in terms of performance, it takes longer time to process large elements e.g N = (3^9)(2^14), M=(2^14)(2^14) for a large element and going a bit higher the performance declines.

Answer 1

I think to brute force this kind of question is the wrong path to take to begin with.

Quoting the wikipedia on Brute Force Search :

While a brute-force search is simple to implement, and will always find a solution if it exists, its cost is proportional to the number of candidate solutions – which in many practical problems tends to grow very quickly as the size of the problem increases. Therefore, brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than speed.

As @WinstonEwert has pointed out, the number of chocolates that you can eat, is related to the least common multiplier. And, here is one fast way of computing it making use of the Euclidean Algorithm :

static int gcf(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

static int lcm(int a, int b)
{
    return (a / gcf(a, b)) * b;
}

Credit to @AffluentOwl's answer

However, LCM is not the final answer, but it is the number of chocolate that we care, we have to divide lcm by M. And, we can simplify all this :

public static int PrintNChocolatesInaCircle(int N, int M)
{
    // these already have a known answer
    if (M == 1) return N;
    if (M == N) return 1;
    
    int a = N, b = M;
    while (b != 0)
    {
        var temp = b;
        b = a % b;
        a = temp;
    }
    
    return N / a;
}

---

Lastly, make sure you respect the requirements :

Write a function:

class Solution { public int solution(int N, int M); }