Solution to Count-Div by codility

16 Apr

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.

41 Replies to “Solution to Count-Div by codility

    • 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!

          • 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

  1. 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/

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

  3. My Swift version

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

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

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

    Greetings.

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

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

  9. 100% solution: Java

  10. esta es mi solucion

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

  12. Here is my 100% solution in python:

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

  14. Python 100%. Time Complexity O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!