Test results - Codility

Tasks Details

easy

1. ChocolatesByNumbers

There are N chocolates in a circle. Count the number of chocolates you will eat.

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:

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].

Solution

Programming language used Java 8

Time spent on task 11 minutes

Notes

not defined yet

Task timeline

Code: 07:55:29 UTC, java, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

// 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
        return N/gcd(N, M);
    }

    private int gcd(int a, int b) {
        int r = a % b;
        // 나머지가 0이면 작은숫자가 최대공약수
        if (r == 0) {
            return b;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자 b와 나머지를 넣어줌
            return gcd(b, r);
        }
    }
}

Analysis

▶

example
example test

✔

Code: 07:55:35 UTC, java, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

// 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
        return N/gcd(N, M);
    }

    private int gcd(int a, int b) {
        int r = a % b;
        // 나머지가 0이면 작은숫자가 최대공약수
        if (r == 0) {
            return b;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자 b와 나머지를 넣어줌
            return gcd(b, r);
        }
    }
}

Analysis

▶

example
example test

✔

Code: 07:55:39 UTC, java, final, score: 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

// 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
        return N/gcd(N, M);
    }

    private int gcd(int a, int b) {
        int r = a % b;
        // 나머지가 0이면 작은숫자가 최대공약수
        if (r == 0) {
            return b;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자 b와 나머지를 넣어줌
            return gcd(b, r);
        }
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(log(N + M))

▶

example
example test

✔

▶

extreme_small
very small N and M

✔

▶

simple
simple test, N = 24, M = 18

✔

▶

small1
small tests

✔

▶

small2
small tests

✔

▶

medium
medium tests

✔

▶

large
large tests

✔

▶

large2
N = (3**9)*(2**14), M=(2**14)*(2**14)

✔

▶

extreme_large
maximal and minimal values

✔