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:
function solution(N, 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].
function solution(N, M) {
// write your code in JavaScript (Node.js 4.0.0)
if(M%N === 0) return 1;
if(N%M === 0) return N/M;
return Math.floor(N/M) + eat(M, N%M);
}
function eat(N,M){
var ate = [];
var pos = 0, count = 0;
while(!ate[pos]){
ate[pos] = true;
count++;
pos = (pos+M)%N;
}
return count;
}function solution(N, M) {
// write your code in JavaScript (Node.js 4.0.0)
if(M%N === 0) return 1;
if(N%M === 0) return N/M;
return Math.floor(N/M) + 1 + eat(M, N%M);
}
function eat(N,M){
var ate = [];
var pos = 0, count = 0;
while(!ate[pos]){
ate[pos] = true;
count++;
pos = (pos+M)%N;
}
return count;
}function solution(N, M) {
// write your code in JavaScript (Node.js 4.0.0)
if(M%N === 0) return 1;
if(N%M === 0) return N/M;
return Math.floor(N/M) + 1 + eat(M, N%M);
}
function eat(N,M){
var ate = [];
var pos = 0, count = 0;
while(!ate[pos]){
ate[pos] = true;
count++;
pos = (pos+M)%N;
}
return count;
}[15, 2]
function solution(N, M) {
// write your code in JavaScript (Node.js 4.0.0)
if(M%N === 0) return 1;
if(N%M === 0) return N/M;
return Math.floor(N/M) + 1 + eat(M, N%M);
}
function eat(N,M){
var ate = [];
var pos = 0, count = 0;
while(!ate[pos]){
ate[pos] = true;
count++;
pos = (pos+M)%N;
}
return count;
}[15, 5]
function solution(N, M) {
// write your code in JavaScript (Node.js 4.0.0)
if(M%N === 0) return 1;
if(N%M === 0) return N/M;
return Math.floor(N/M) + 1 + eat(M, N%M);
}
function eat(N,M){
var ate = [];
var pos = 0, count = 0;
while(!ate[pos]){
ate[pos] = true;
count++;
pos = (pos+M)%N;
}
return count;
}[15, 4]
function solution(N, M) {
// write your code in JavaScript (Node.js 4.0.0)
if(M%N === 0) return 1;
if(N%M === 0) return N/M;
var ate = [];
var pos = 0, count = 0;
while(!ate[pos]){
ate[pos] = true;
count++;
pos = (pos+M)%N;
}
return count;
}[15, 4]
function solution(N, M) {
// write your code in JavaScript (Node.js 4.0.0)
if(M%N === 0) return 1;
if(N%M === 0) return N/M;
var ate = [];
var pos = 0, count = 0;
while(!ate[pos]){
ate[pos] = true;
count++;
pos = (pos+M)%N;
}
return count;
}[15, 4]
The following issues have been detected: timeout errors.
For example, for the input (415633212, 234332) the solution exceeded the time limit.
FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memorystdout:
<--- Last few GCs --->
112 ms: Scavenge 3.5 (39.0) -> 3.3 (39.0) MB, 1.1 / 0 ms [allocation failure].
1257 ms: Mark-sweep 131.7 (166.6) -> 99.1 (136.0) MB, 36.2 / 0 ms [allocation failure] [GC in old space requested].
1292 ms: Mark-sweep 99.1 (136.0) -> 99.1 (136.0) MB, 34.5 / 0 ms [allocation failure] [GC in old space requested].
1326 ms: Mark-sweep 99.1 (136.0) -> 99.1 (136.0) MB, 34.6 / 0 ms [last resort gc].
1361 ms: Mark-sweep 99.1 (136.0) -> 98.9 (136.0) MB, 34.2 / 0 ms [last resort gc].
<--- JS stacktrace --->
==== JS stack trace =========================================
Security context: 0x48054f36a81 <JS Object>
1: solution(aka solution) [/tmp/solution.js:~1] [pc=0xbbe756bf884] (this=0x48054f04131 <undefined>,N=415633212,M=234332)
2: run(aka run) [/tmp/user.js:213] [pc=0xbbe756bbe12] (this=0x48054f04131 <undefined>,input=0x2d61a8b5ac99 <String[7]: data.in>,output=0x2d61a8b5acb9 <String[8]: data.out>)
3: main(aka main) [/tmp/user.js:232] [pc=0xbbe756b8ac2] (this=0x48054f04131 <undefined>)
...