Question: https://codility.com/demo/take-sample-test/count_div

Question Name: Count-Div or CountDiv

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

1 2 3 | def solution(A, B, K): if A % K == 0: return (B - A) // K + 1 else: return (B - (A - A % K )) // K |

(Java)

return B / K – (A / K) + (A % K == 0 ? 1 : 0);

And yes, its very simple for two stars!

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

scratch that, I messed up the code port!

That is fine. Enjoy coding!

completely a mathematic question

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

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.

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!

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

Pretty Pythonic! Thanks!

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

It should be two: 0 and 3.

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

Yes, especially this:

(B – (A – A % K ))

it’s obvious as hell…

Math Maze.

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.

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:

Link to codility:

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

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:

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]

My Swift version

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:

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

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

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

Greetings.

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

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: