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.

23 thoughts on “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!

  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

Leave a Reply

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