# Solution to Count-Div by codility

16 Apr

Question Name: Count-Div or CountDiv

It is completely a mathematic question. Not qualified for a 2-star problem.

### 40 Replies to “Solution to Count-Div by codility”

1. van says:

(Java)
return B / K – (A / K) + (A % K == 0 ? 1 : 0);
And yes, its very simple for two stars!

2. Marc says:

Posted solution does not work for A=6, B=11, K=6. Returns 0, should return 1.

• Marc says:

scratch that, I messed up the code port!

• Sheng says:

That is fine. Enjoy coding!

3. Lukasz says:

completely a mathematic question
This doesn’t seem obvious, can you please provide some reference to the proof/theory?

• Sheng says:

It is just my personal opinion and may be wrong 🙂
Because the code is really simple. As long as you get the idea with math, coding is completely not a challenge.

• Rachel says:

Clearly the size of the interval [A,B] determines the answer, however we distinguish the two different cases because whether or not K divides A affects the answer. Take K=10 for example. If A=20 and B=30 then the answer is 2. If A=21 and B=31 then the answer is 1 despite the fact that the difference A-B here is the same. Since K divides A in the first instance the answer is one greater.
Now, let a = A%K (i.e. A = a (mod K))
so we may write A = a + mK for some integer m
here mK is the largest multiple of K that is less than or equal to A
and A – A%K = a + mK – a = mK
(note if A is a multiple of K then a=0)
the number of multiples of K in [A,B] is the same as the number of multiples of K in [mK,B] if a=0 (i.e. K divides M) and one less than this if a>0 (i.e. K doesn’t divide M), because in this case mK is not in the interval [A,B]
Now, the number of multiples of K in [mK,B] is equal to the number of multiples of K in the interval [0,B-mK], which is floor((B-mK)/K) +1 (the plus one is there because 0 is a multiple)
so the answer is
(B-(A-A%K))//K if A%K>0
and
(B-(A-A%K))//K + 1 = (B-A)//K + 1 if A%K==0
I hope my explanation makes sense!

• Sheng says:

I sincerely appreciate your work to make the idea so clear!

• Hemaraj says:

I can’t understand can u please explain..

• Sheng says:

Sorry, I cannot make a proof, more clear than Rachel’s. Maybe you can have a paper and pen, try to draw something as solving a math problem.

• raul says:

I don’t think that anyone will be able to give you a more complete answer then Rachel did, although I’ll try to make it simpler:

The answer is certanly in the difference between A and B ([A,B]), but we can’t rely on this difference alone since we may have cases where the same difference for the same K will give us 2 different answers. Rachel gave us a good example: A=20, B=30 and K=10 should return 2, with a difference of 10 between A and B. Although, A=21, B=31 and K=10 should return 1 despite the fact that [A,B] is still 10 and K haven’t changed.

So, let’s think a bit: if we take the rest of the division of A by K (A%K) out of A (A – A%K), we will have the closest number to A that is still divisible by K (mK). And if we take mK out of B (B-mK) we will always have the same interval between 0 and B-mK ([0, B-mK]) if two differents A and B have the same interval. Now we can count the multiples of K inside [0, B-mK] by dividing (B-mk) by K ((B-mK)/K), just like you would do to find out which number multiplied by 3 would give you 27 (27/3), althogh you have to remember that 0 still counts as divisible by K no matter what the value of K is, so we have to add this value by making it (B-mK)/K + 1.
But, remember that if A%B>0, you have a multiple of K that shouldn’t be there. In that case, mK just doesn’t exist, insted of A%B==0 where mK and A are the same (mK == A). So in A%B>0 it will be (B-mK)/K + 1 – 1 which is the same as (B-mK)/K.

Now, remember that mk is A – A%K, which can make the formula become (B-A)/K or (B-(A – A%K))/K + 1 depending on whether A%K is greater or equal to zero, leading to Sheng’s code:

Note that we we use floor division (//) so our answer will be an integer and we don’t depend on B – (A – A % K ) being a multiple of K.

But in python you can actully make it even simpler since in math operations python sees True and False as 1 and 0, and A – A % K is equal A if A % K == 0, and that leads to my code:

• raul says:

Sorry, on (B-A)/K or (B-(A – A%K))/K + 1 it should’ve been (B-(A – A%K))/K or (B-A)/K + 1

4. Mathieu says:

• Sheng says:

Pretty Pythonic! Thanks!

• William says:

This solution is not valid for A=0, B=5, K=3. It returns 2, but should return 1.

• Sheng says:

It should be two: 0 and 3.

• Craig says:

I got this same solution, but it averages three division operations, while Sheng’s is two.

5. mat says:

Yes, especially this:
(B – (A – A % K ))
it’s obvious as hell…

• Sheng says:

Math Maze.

• Craig says:

It is not obvious, but if you think about it, it is basically moving the left boundary to the last time it was divisible by K. Then you can know if any extra of the ints within A and B that is also divisible by K.

6. Roberto Gonzalez says:

Adding a 100% Java solution with some test cases before the signature method if you want to test your solutions first before seeing the solution:

https://codility.com/demo/results/demoWFBKU8-SNV/

7. KEMBL says:

C# 75% – but it seems some issue with checking, because there is no way to expect 0 in given case:

and second mistake, I believe, because of leading K > B check, I have no idea why they make this test:

• Sheng says:

Try to print out the input, and you will know why you were wrong.
Try the testing case: [10, 10, 7] and [0, 0, 11]

8. Vladimir Cezar says:

My Swift version

9. Bogdan says:

As this test is under “Prefix Sums” category, here is a prefix sums solution. Obviously, the performance do not pass, is O(N) not O(1). It even fails on big numbers as of not enough memory.
But I think is good as a theoretical algorithm:

• Sheng says:

Sorry, I cannot agree with you. Both time and space complexity of this solution is worse.

10. micropentium6 says:

Using 0 as the base, count numbers of “divisible by K” int range [0, B] as M and [0, A] as N.
M – N is the answer if A is not “divisible by K”. Otherwise, M – N excludes counting A as “divisible by K”, therefore M – N + 1

11. Jose Manuel says:

Here my solution in Java. I think is very clear and clean. It works 100% with O(1) time complexity.

Greetings.

• Chema says:

I am losing my faith in the human being… O(1) time complexity with a While loop in your algorithm…

12. Samuel says:

I was able to solve the problem using arithmetic progression (https://en.wikipedia.org/wiki/Arithmetic_progression). I’ve had to add a special case for 0, which I can’t explain but it was based on the test results:

13. mE says:

This is a solution I got. It’s not the most beautiful code ever but it works.

14. Roman says:

100% solution: Java

15. marlon says:

esta es mi solucion

16. Sourabh says:

If the python % and // are not easily understandable for someone, here’s a more readable solution in JS.

17. Joy says:

100% for Python~

18. Paaksing says:

Here is my 100% solution in python:

19. Chesstrian says:

Given any two natural numbers, the number of divisors is exactly the natural division between them:

In order to get the number of divisors between two numbers, you only need to calculate the numbers of divisors of the bigger number and then subtract the number of divisors of the smaller number, however, since the smaller number can be count, we calculate the number of divisor of the smaller number minus one:

which is exactly the same solution shared by Sourabh and Joy.

20. Wenqi says:

haha, a complete math question I would teach elementary school kids.
my code (link below) is not one line, but it’s reader friendly.
https://app.codility.com/demo/results/training2SK2T4-7QW/