2
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You do not need the if (N == 0) check, read the assumptions. \$\endgroup\$ Jun 13, 2016 at 16:27
  • \$\begingroup\$ OOps good spot on , that skipped my mind. I will update my code \$\endgroup\$
    – Tolani
    Jun 13, 2016 at 16:31
  • \$\begingroup\$ Have you tried applying @winstons's suggestions from the question you linked to? They seem pretty language agnostic. \$\endgroup\$
    – forsvarir
    Jun 13, 2016 at 17:10
  • \$\begingroup\$ Part of your performance issue is that you double calculate (start + M) % N, store this somewhere in a variable and you'll likely see a large decrease in time taken. \$\endgroup\$ Jun 13, 2016 at 17:56

1 Answer 1

5
\$\begingroup\$

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); }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.