Codility CountDiv

We are asked to write a function that tells how many integers in a given interval are divisible by a given number.

The solution is very easy, if you don't get confused by the fact that this problem is in the Codility Prefix Sum section.

You could actually devise an implementation that makes use of partial sum, but it is not the right direction. An hint is that the expected complexity should be constant in time and size.

Let's write a couple of test cases (C++ for GoogleTest) while thinking to a better solution:

TEST(CountDiv, Given) // 1
{
    ASSERT_EQ(3, solution(6, 11, 2));
}

TEST(CountDiv, Minimal) // 2
{
    ASSERT_EQ(1, solution(0, 1, 3));
}

TEST(CountDiv, BothSides)
{
    ASSERT_EQ(7, solution(0, 12, 2));
}

1. Codility provided test case. In the interval [6, 11] there are 3 numbers divisible by 2: 6, 8, 10.
2. Remember that you can divide zero by any numbers, so in [0, 1] there is one number (zero) divisible by three.
3. A simple case, we want to check all the integer in [0 .. n].

And here is a possible solution:

int solution(int first, int last, int div)
{
    return (last / div) - (first / div) + !(first % div);
}

Firstly I get how many integers up to the end are divisible by div, then subtract the ones to the left. But remember to add the left limit, if it is needed.

***

You could think of saving some processor seeing that "div" is the dividend for both "last" and "first", and rewriting it as a single division. After all, we know that:

(A / C) - (B / C) = (A - B) / C

Right?

Yes, if we worked on floating point numbers. However, here we have integers, so we are applying the integer division operator, discarding each time the remaind, and having (sometimes) a different result from the floating point division operator applied to the same values.

For instance consider this test case:

TEST(CountDiv, Single)
{
    ASSERT_EQ(1, solution(6, 11, 7));
}

Here we are looking for the divisors of 7 in the interval [6, 11]. It is easy to spot that the solution is one, value 7 should be accepted. Applying the integer division to "last" and "first", we are actually answering to the question "how many values have seven as divisor in the interval [1, X]?"

In this context we can't apply the distributive property of division, because we are not working on the realm of real numbers.

We can't apply subtraction on "last" and "first" and then divide the result by 7, because this would mean that we are checking the size of the interval from "first" to "last" against 7.

If I try to be smarter that required, calculating (11 - 6) / 7, I get a zero. I'm not checking if there is a number in the interval that could be divided by 7, I'm checking how big is the interval compared to 7.