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!
I can’t understand can u please explain..
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.
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:
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
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:
This is a solution I got. It’s not the most beautiful code ever but it works.
100% solution: Java
esta es mi solucion
If the python % and // are not easily understandable for someone, here’s a more readable solution in JS.
100% for Python~
Here is my 100% solution in python:
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.
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/
Python 100%. Time Complexity O(1).