Codility ‘CountDiv’ Solution

Posted on by
Short Problem Definition:

Compute number of integers divisible by k in range [a..b].

Link

CountDiv

Complexity:

expected worst-case time complexity is O(1);

expected worst-case space complexity is O(1)

Execution:

This little check required a bit of experimentation. One needs to start from the first valid value that is bigger than A and a multiply of K.

Solution:
def solution(A, B, K):
    if B < A or K <= 0:
        raise Exception("Invalid Input")

    min_value =  ((A + K -1) // K) * K

    if min_value > B:
      return 0

    return ((B - min_value) // K) + 1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Dusan Orlovic

    solution could be simpler, for example in ruby

    def solution(a, b, k)
    b/k – (a-1)/k

    end

    • I solved it by visualising the numbers on a grid. Is your version always correct?

      • Dusan Orlovic

        Yes, it’s 100%.
        Thanks for very nice explanations of other solutions…

  • Cassius

    Using Dusan solution for Python, it works 100%.

    My question is if (A,B,K) = (6,12,2), shouldn’t the answer be 3? and not 4?

    Why does the Python shell spit out 4?

    • disqus_zCuXFoPKQV

      Because the following values are divisible by 2:
      6, 8, 10, 12

  • Paul Tomblin

    This one got me 100%.

    diffs = B/K – A/K

    if A % K == 0:

    diffs += 1

    return diffs

  • Could you please explain why this problem is placed inside the “prefix sums” category?

  • Tanuj Sharma

    Java 100%/100%

    class Solution {
    public int solution(int A, int B, int K) {

    if(A == 0 && B==0){
    return 1;
    } else if(A==0){
    return B/K+1;
    }

    return (B/K-(A-1)/K);
    }
    }