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.

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

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