# Codility - Count Divisible

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

Definitions:
$\{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\}$

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

### Analysis:

The solution to this problem is pretty simple, the integers divisible by K, are the ones described by $a.K,\, a \in \mathbb{N}^*$. $B/K$ gives us all divisible integers from 1 to B, $\{0,..,1k,...,2k,...,3k,..,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: Count Divisible Python # Name: CountDiv # Link: https://codility.com/demo/take-sample-test/count_div/ def solution(A, B, K): # B//K Al numbers divisible by K from 0 to B, (A - 1)//K # all number divisible by K except A if A is divisible return B//K - (A - 1)//K 12345678 # Name: CountDiv# Link: https://codility.com/demo/take-sample-test/count_div/  def solution(A, B, K):    # B//K Al numbers divisible by K from 0 to B, (A - 1)//K     # all number divisible by K except A if A is divisible    return B//K - (A - 1)//K

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