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.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..1,000,000,000].
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout 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 temp = N;
int R = N / M;
while (N % M != 0) {
// System.out.println("N % M == 0 : " + (N % M != 0));
R = N % M;
N = M;
M = R;
// System.out.println("R : " + (R));
// System.out.println("N : " + (N));
// System.out.println("M : " + (M));
}
return M * R == N ? R : temp / R;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout 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 temp = N;
int R = N / M;
if(M * R == N){
return R;
}
while (N % M != 0) {
// System.out.println("N % M == 0 : " + (N % M != 0));
R = N % M;
N = M;
M = R;
// System.out.println("R : " + (R));
// System.out.println("N : " + (N));
// System.out.println("M : " + (M));
}
return temp / R;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout 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 temp = N;
int R = N / M;
if(M * R == N){
return R;
}
while (N % M != 0) {
// System.out.println("N % M == 0 : " + (N % M != 0));
R = N % M;
N = M;
M = R;
// System.out.println("R : " + (R));
// System.out.println("N : " + (N));
// System.out.println("M : " + (M));
}
return temp / R;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout 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 temp = N;
int R = N / M;
if(M * R == N){
return R;
}
while (N % M != 0) {
// System.out.println("N % M == 0 : " + (N % M != 0));
R = N % M;
N = M;
M = R;
// System.out.println("R : " + (R));
// System.out.println("N : " + (N));
// System.out.println("M : " + (M));
}
return temp / R;
}
}
The solution obtained perfect score.