---
# System prepended metadata

title: L12-ChocolatesByNumbers
tags: [Codility_lessons]

---

# L12-ChocolatesByNumbers
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/12-euclidean_algorithm/chocolates_by_numbers/
## Key
會一直在N範圍內吃巧克力，直到碰到包裝紙(%N = 0)，法一比較快，法二比較直觀，但比較慢
## Reference
## Solution
```cpp=
int gcdByDivision(int A, int B) {
    if (A % B == 0)
        return B;
    else
        return gcdByDivision(B, A % B);
}

int solution(int N, int M) {
    return N / gcdByDivision(N, M);
}
```

```cpp=
int solution(int N, int M) {
    int counter = 1;
    int start = 0;
    int value;
    while ((start + M) % N != 0)
    {
        value = (start + M) % N;
        start = value;
        counter++;
    }
    return counter;
}
```
