Solution to Codility lesson3-exercise1 Count Divisible problem, link to Codility problem and complete solution at the end of the post.


    \[\{K \in \mathbb{N}\ |\ 1\leq A,B \leq 1,000,000,000\}\]

    \[\{A,B \in \mathbb{N}\ |\ 0\leq A,B \leq 2,000,000,000\land A\leq B\}\]

Define a function solution with input A, B and K, such that solution returns the number of integers divisible by , belonging to the interval [A, B].

  • Expected worst-case time complexity is O(1);
  • Expected worst-case space complexity is O(1);

Elements of input arrays can be modified. 


The solution to this problem is pretty simple, the integers divisible by K, are the ones described by

    \[a.K,\, a \in \mathbb{N}^*\]



 gives us all divisible integers from 1 to B,


Now we just have to subtract the integers that dot not belong to the interval [A, B]. We have to be careful here, since A belongs to the interval, if A is divisible we have count it, so when excluding, we are going to do

    \[(A - 1)/K\]

. And the solution is

    \[B/K-(A - 1)/K\]

We are doing only one operation to solve this problem, so this gives us, time complexity and space complexity of O(1);

Complete Solution:

Time Complexity O(1)
Space Complexity O(1)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/