There are N chocolates in a circle. Count the number of chocolates you will eat.
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:
func Solution(N int, M int) int
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].
Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
N塊巧克力,如果吃的是X號 下一個是吃 (X + M) modulo N 號 總共可以吃幾顆.
方法ㄧ: 從0號開始吃, 下一個號碼+M-1號. 迴圈去跑 方法二: 可以吃到的巧克力的數量就是總的巧克力顆數 N 除以 N 和 M 的最大公因數. 計算 N和M的最大公因數P, N除以P得到商即為答案
https://app.codility.com/programmers/lessons/12-euclidean_algorithm/chocolates_by_numbers/
package chocolatesbynumbers
func gcd(N int, M int) int {
if N%M == 0 {
return M
} else {
return gcd(M, N%M)
}
}
/*
可以吃到的巧克力的數量就是總的巧克力顆數 N 除以 N 和 M 的最大公因數
計算 N和M的最大公因數P, N除以P得到商即為答案
O(log(N + M))
*/
func Solution(N int, M int) int {
return N / gcd(N, M)
}
/*
Task Score 75%
Correctness 100%
Performance 50%
input (947853, 4453) the solution exceeded the time limit.
從0號開始吃, 下一個號碼+M-1號
*/
func SolutionBurst(N int, M int) int {
eaten := make(map[int]struct{})
eatCount := 0
if N == 1 || M == 1 {
return N
}
for {
sumNum := eatCount * M
startNum := sumNum % N
if _, ok := eaten[startNum]; !ok {
eaten[startNum] = struct{}{}
eatCount++
} else {
// 找到已吃過的巧克力
break
}
}
return eatCount
}