Codility test - find multiples in range

user_2669338 0
Viewed 21558

I applied for a job and was asked to do a Codility test. The test was the following:

Return the number of integers within the range [A..B] that are divisible by K.

Args:

  • A: is an integer within the range [0..2,000,000,000]
  • B: is an integer within the range [0..2,000,000,000] and A <= B
  • K: is an integer within the range [1..2,000,000,000]

Time complexity must be O(1).

I know my solution isn't O(1), I couldn't come up with a better solution than this. Can anyone enlighten me?

BTW, it's in C# so 'int' is large enough to hold 2000000000.

public int solution(int A, int B, int K) 
{
    int i=0;

    for(int x=A;x<=B;x++)
    {
        if((x % K) == 0)
            i++;
    }

    return i;
}
time-complexity algorithm c#
10 Answers

A much more efficient way is to simple produce multiples of C from A to B so you do not need to check each value necessarily. The large the C the more efficient it will be.

do 
{
    int a = start + (C * i++);
    if (a >= A && a <= B)
    {
        //display a;
    }
    if (a > B)
        break;
}while (true);
user_56479470

You can use Java11 stream API to solve this.

public long solution(int A, int B, int K) {
    return IntStream.iterate(A, n -> n <= B, n -> n+1)
                    .filter(n -> n%k==0)
                    .count();
}

The benefit of using Java Stream API is that we can make the stream parallel for better performance if we have a large dataset.

user_36493520
Related