Codility 'ChocolatesByNumbers' Solution | MartinKysel.com
https://github.com/acprimer/Codility/blob/master/src/Lesson10/ChocolatesByNumbers.java
public int solution(int N, int M) {
return N / gcd(N, M);
}
private int gcd(int n, int m) {
int r = n % m;
while (r != 0) {
n = m;
m = r;
r = n % m;
}
return m;
}
http://codility-lessons.blogspot.com/2015/03/lesson-10-chocolatesbynumbers.html
We have to stop eating more chocolates when we reached the same location we visited before. So the answer will be 'the least common multiple of N and M(LCM) / M'. As LCM can be computed by (N * M) / gcd(N,M), LCM / M = (N * M) / gcd(N, M) / M = N / gcd(N, M).
If someone feel the above is unclear imagine such a situation below.
location (N = 7): 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0
position (M = 4): X X X X X X X X
As above, we reach the same location at the LCM of N and M.
http://codesays.com/2014/solution-to-chocolates-by-numbers-by-codility/
When we met with an empty wrapper, we must have been this position for twice. We use i for the first time and j for the second time. Due to the modulo feature, there must be nature number, to say k, so that: i * M + k * N = j * M. Then we could easily prove that the smallest (earliest) i must be zero (for all i != 0, then (i-i) * M + k * N = (j-i) * M ). So the first eaten position would be first position that you meet again. Finally, the j would be the number of chocolates that you will eat.
Read full article from Codility 'ChocolatesByNumbers' Solution | MartinKysel.com
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.
N and M meet at their least common multiply. Dividing this LCM by M gets the number of steps(chocolates) that can be eaten.def gcd(p, q): if q == 0: return p return gcd(q, p % q)def lcm(p,q): return p * (q / gcd(p,q))def solution(N, M): return lcm(N,M)/M |
1
2
3
4
5
6
7
8
9
10
| def naive(N,M): eaten = [False] * N at = 0 cnt = 0 while eaten[at] != True: eaten[at] = True at = (at + M) % N cnt += 1 return cnt |
public int solution(int N, int M) {
return N / gcd(N, M);
}
private int gcd(int n, int m) {
int r = n % m;
while (r != 0) {
n = m;
m = r;
r = n % m;
}
return m;
}
http://codility-lessons.blogspot.com/2015/03/lesson-10-chocolatesbynumbers.html
We have to stop eating more chocolates when we reached the same location we visited before. So the answer will be 'the least common multiple of N and M(LCM) / M'. As LCM can be computed by (N * M) / gcd(N,M), LCM / M = (N * M) / gcd(N, M) / M = N / gcd(N, M).
If someone feel the above is unclear imagine such a situation below.
location (N = 7): 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0
position (M = 4): X X X X X X X X
As above, we reach the same location at the LCM of N and M.
http://codesays.com/2014/solution-to-chocolates-by-numbers-by-codility/
When we met with an empty wrapper, we must have been this position for twice. We use i for the first time and j for the second time. Due to the modulo feature, there must be nature number, to say k, so that: i * M + k * N = j * M. Then we could easily prove that the smallest (earliest) i must be zero (for all i != 0, then (i-i) * M + k * N = (j-i) * M ). So the first eaten position would be first position that you meet again. Finally, the j would be the number of chocolates that you will eat.
2
3
4
5
6
7
8
9
10
|
def gcd(a, b):
# Get the greatest common divisor
if (a % b == 0):
return b
else:
return gcd(b, a % b)
def solution(N, M):
lcm = N * M / gcd(N, M) # Least common multiple
return lcm / M
|
