Test results - Codility

Tasks Details

medium

1. CountDiv

Compute number of integers divisible by k in range [a..b].

100%

Write a function:

class Solution { public int solution(int A, int B, int K); }

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

A and B are integers within the range [0..2,000,000,000];

K is an integer within the range [1..2,000,000,000];

A ≤ B.

Solution

Programming language used Java 8

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 04:21:13 UTC, java, final, score: 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution {
    public int solution(int A, int B, int K) {
        // write your code in Java SE 8
        int cnt = 0;
        for(int i=A; i<=B; i++){
            if(i%K == 0){
                cnt++;
                cnt += (B - i) / K;
                break;
            }
        }
        return cnt;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(1)

▶

example
A = 6, B = 11, K = 2

✔

▶

simple
A = 11, B = 345, K = 17

✔

▶

minimal
A = B in {0,1}, K = 11

✔

▶

extreme_ifempty
A = 10, B = 10, K in {5,7,20}

✔

▶

extreme_endpoints
verify handling of range endpoints, multiple runs

✔

0.004 s

▶

big_values
A = 100, B=123M+, K=2

✔

▶

big_values2
A = 101, B = 123M+, K = 10K

✔

▶

big_values3
A = 0, B = MAXINT, K in {1,MAXINT}

✔

▶

big_values4
A, B, K in {1,MAXINT}

✔