“ChocolatesByNumbers” challenge

Question

Here is a problem I have attempted:

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))\$

The results show that it's not that efficient. How can I make it more efficient? What's wrong with my approach?

import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N, int M) {
        // write your code in Java SE 8

    int answer =1;
    HashMap<Integer , Integer> som = new HashMap<>();
    boolean check = true;
    int x =0;
    som.put(0,0);
    while(check)
    {

       int  m = (x+ M) % N ;
        x = m;
        if(som.containsKey(x))
         check = false;
         else
         {
             som.put(x,0);
             answer++;
         }
    }
    return answer;
    }

Answer 1

In these sorts of problems you can't take the simple approach, you've got to come up with a clever way to avoid actually simulating the eating of the candy bars.

Some hints for practice see how few hints you can use.

1. Try printing out which bars are eaten and see if you can see a pattern.

2. In your samples look at which candy bar is the first one repeated.

3. You can prove this result by considering what happens after you've started repeating candy bars, and considering whether or not other ways of reaching the final position are possible.

4. Can you express the rule for when the cycle repeats mathematically?

5. Do you know the mathematical name for the first number that fits the rule?

6. Its LCM

Answer 2

Comments about your existing code:

• Your indentation is way off
• It is good practice to declare a variable by interface and not an implementation, so Map<Integer, Integer> variable = new HashMap<>();
• You're using your Map as a Set, so you can use Set<Integer> som = new HashSet<>(); instead
• Your variable names stink (no offense, but really... why the name 'som'? why 'x'? etc.)
• Instead of your check variable you can use break; to break out of the while loop.
• Your m variable is only used to set the new value for x so you don't need it at all.
• Always use braces, even if it's only one statement you want to perform.
• Your existing comments are totally unnecessary and just noisy.
• It is better to only include specific classes instead of using .* in an import.

Here's the improved code, with all of the above fixed:

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int N, int M) {
        int answer = 1;
        Set<Integer> eatenChocolates = new HashSet<>();
        int currentChocolate = 0;
        eatenChocolates.add(0);
        while (true) {
            currentChocolate = (currentChocolate + M) % N;
            if (eatenChocolates.contains(currentChocolate)) {
                break;
            }
            else {
                eatenChocolates.add(currentChocolate);
                answer++;
            }
        }
        return answer;
    }
}