Tasks Details
easy
There are N chocolates in a circle. Count the number of chocolates you will eat.
Task Score
100%
Correctness
100%
Performance
100%
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:
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].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 20 minutes
Notes
not defined yet
Task timeline
Code: 12:50:06 UTC,
java,
autosave
Code: 12:50:06 UTC,
java,
autosave
Code: 12:53:58 UTC,
cpp,
autosave
Code: 12:54:14 UTC,
cpp,
autosave
Code: 12:54:35 UTC,
cpp,
autosave
Code: 12:55:01 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
}
}
Code: 12:56:55 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
}
}
Code: 13:01:59 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
}
}
Code: 13:02:17 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
}
}
Code: 13:02:27 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
}
}
Code: 13:02:37 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
int idx = i*
}
}
Code: 13:02:48 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
int idx = i*M
}
}
Code: 13:03:36 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
int idx = i(*M
}
}
Code: 13:04:05 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
int idx = (i*M)%M;
eat_flag[idx] = false;
}
}
Code: 13:04:18 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
int idx = (i*M)%M;
eat_flag[idx] = 1;
}
}
Code: 13:04:30 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
int idx = (i*M)%M;
if()
eat_flag[idx] = 1;
}
}
Code: 13:04:49 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
for(int i=0; i<N; i++){
int idx = (i*M)%M;
if(eat_flag[idx] == 0){
eat_flag[idx] = 1;
}eat_flag[idx] = 1;
eat_flag[idx] = 1;
}
}
Code: 13:05:17 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
int count = 0;
for(int i=0; i<N; i++){
int idx = (i*M)%M;
if(eat_flag[idx] == 0){
eat_flag[idx] = 1;
count++;
}eat_flag[idx] = 1;
eat_flag[idx] = 1;
}
}
Code: 13:05:32 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
int count = 0;
for(int i=0; i<N; i++){
int idx = (i*M)%M;
if(eat_flag[idx] == 0){
eat_flag[idx] = 1;
count++;
}else{
eat_flag[idx] = 1;
}
}
}
Code: 13:05:44 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
int count = 0;
for(int i=0; i<N; i++){
int idx = (i*M)%M;
if(eat_flag[idx] == 0){
eat_flag[idx] = 1;
count++;
}else{
break;
}
}
}
Code: 13:05:52 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
vector<int> eat_flag(N, 0);
int count = 0;
for(int i=0; i<N; i++){
int idx = (i*M)%M;
if(eat_flag[idx] == 0){
eat_flag[idx] = 1;
count++;
}else{
break;
}
}
return count;
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got 1 expected 5
Code: 13:06:46 UTC,
cpp,
autosave
Code: 13:07:16 UTC,
cpp,
autosave
Code: 13:07:27 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
}
int calc_gcd(int a, int b){
if(a == b){
return
}
}
Code: 13:07:45 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
}
int calc_gcd(int a, int b){
if(b == 0){
return a;
}
}
Code: 13:08:08 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
}
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc
}
}
Code: 13:08:20 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
}
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc_gcd(b, a%b)
}
}
Code: 13:08:42 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
}
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc_gcd(b, a%b);
}
}
Code: 13:09:08 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc_gcd(b, a%b);
}
}
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
int gcd = calc_gcd(N, M);
}
Code: 13:09:27 UTC,
cpp,
autosave
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc_gcd(b, a%b);
}
}
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
int gcd = calc_gcd(N, M);
int res = N/gcd;
}
Code: 13:09:33 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc_gcd(b, a%b);
}
}
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
int gcd = calc_gcd(N, M);
int res = N/gcd;
return res;
}
Analysis
Code: 13:09:50 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc_gcd(b, a%b);
}
}
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
int gcd = calc_gcd(N, M);
int res = N/gcd;
return res;
}
Analysis
Code: 13:09:55 UTC,
cpp,
final,
score:
100
// you can use includes, for example:
#include <bits/stdc++.h>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int calc_gcd(int a, int b){
if(b == 0){
return a;
}else{
return calc_gcd(b, a%b);
}
}
int solution(int N, int M) {
// write your code in C++14 (g++ 6.2.0)
int gcd = calc_gcd(N, M);
int res = N/gcd;
return res;
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(log(N + M))
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
expand all
Performance tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK