How to find the number of values in a given range divisible by a given value?

I have three numbers x, y , z.

For a range between numbers x and y.

How can i find the total numbers whose % with z is 0 i.e. how many numbers between x and y are divisible by z ?

Solution 1:

It can be done in O(1): find the first one, find the last one, find the count of all other.

I'm assuming the range is inclusive. If your ranges are exclusive, adjust the bounds by one:

find the first value after x that is divisible by z. You can discard x:
```
x_mod = x % z;

if(x_mod != 0)
  x += (z - x_mod);
```
find the last value before y that is divisible by y. You can discard y:
```
y -= y % z;
```

find the size of this range:

if(x > y)
  return 0;
else
  return (y - x) / z + 1;

If mathematical floor and ceil functions are available, the first two parts can be written more readably. Also the last part can be compressed using math functions:

 x = ceil  (x, z);
 y = floor (y, z);
 return max((y - x) / z + 1, 0);

if the input is guaranteed to be a valid range (x >= y), the last test or max is unneccessary:

 x = ceil  (x, z);
 y = floor (y, z);
 return (y - x) / z + 1;

Solution 2:

^{(2017, answer rewritten thanks to comments)}
The number of multiples of z in a number n is simply n / z

/ being the integer division, meaning decimals that could result from the division are simply ignored (for instance 17/5 => 3 and not 3.4).

Now, in a range from x to y, how many multiples of z are there?

Let see how many multiples m we have up to y

0----------------------------------x------------------------y
-m---m---m---m---m---m---m---m---m---m---m---m---m---m---m---

You see where I'm going... to get the number of multiples in the range [ x, y ], get the number of multiples of y then subtract the number of multiples before x, (x-1) / z

Solution: ( y / z ) - (( x - 1 ) / z )

Programmatically, you could make a function numberOfMultiples

function numberOfMultiples(n, z) {
   return n / z;
}

to get the number of multiples in a range [x, y]

numberOfMultiples(y) - numberOfMultiples(x-1)

The function is O(1), there is no need of a loop to get the number of multiples.

Examples of results you should find

[30, 90] ÷ 13 => 4
[1, 1000] ÷ 6 => 166
[100, 1000000] ÷ 7 => 142843
[777, 777777777] ÷ 7 => 111111001

For the first example, 90 / 13 = 6, (30-1) / 13 = 2, and 6-2 = 4

---26---39---52---65---78---91--
     ^                      ^
     30<---(4 multiples)-->90

Solution 3:

I also encountered this on Codility. It took me much longer than I'd like to admit to come up with a good solution, so I figured I would share what I think is an elegant solution!

Straightforward Approach 1/2:

O(N) time solution with a loop and counter, unrealistic when N = 2 billion.

Awesome Approach 3:

We want the number of digits in some range that are divisible by K.

Simple case: assume range [0 .. n*K], N = n*K

N/K represents the number of digits in [0,N) that are divisible by K, given N%K = 0 (aka. N is divisible by K)

ex. N = 9, K = 3, Num digits = |{0 3 6}| = 3 = 9/3

Similarly,

N/K + 1 represents the number of digits in [0,N] divisible by K

ex. N = 9, K = 3, Num digits = |{0 3 6 9}| = 4 = 9/3 + 1

I think really understanding the above fact is the trickiest part of this question, I cannot explain exactly why it works. The rest boils down to prefix sums and handling special cases.

Now we don't always have a range that begins with 0, and we cannot assume the two bounds will be divisible by K. But wait! We can fix this by calculating our own nice upper and lower bounds and using some subtraction magic :)

First find the closest upper and lower in the range [A,B] that are divisible by K.
- Upper bound (easier): ex. B = 10, K = 3, new_B = 9... the pattern is B - B%K
- Lower bound: ex. A = 10, K = 3, new_A = 12... try a few more and you will see the pattern is A - A%K + K
Then calculate the following using the above technique:
- Determine the total number of digits X between [0,B] that are divisible by K
- Determine the total number of digits Y between [0,A) that are divisible by K
Calculate the number of digits between [A,B] that are divisible by K in constant time by the expression X - Y

Website: https://codility.com/demo/take-sample-test/count_div/

class CountDiv {
    public int solution(int A, int B, int K) {
        int firstDivisible = A%K == 0 ? A : A + (K - A%K);
        int lastDivisible = B%K == 0 ? B : B - B%K; //B/K behaves this way by default.
        return (lastDivisible - firstDivisible)/K + 1;
    }
}

This is my first time explaining an approach like this. Feedback is very much appreciated :)

Solution 4:

This is one of the Codility Lesson 3 questions. For this question, the input is guaranteed to be in a valid range. I answered it using Javascript:

function solution(x, y, z) {
    var totalDivisibles =  Math.floor(y / z),
        excludeDivisibles = Math.floor((x - 1) / z),
        divisiblesInArray = totalDivisibles - excludeDivisibles;
   return divisiblesInArray;
}

https://codility.com/demo/results/demoQX3MJC-8AP/

(I actually wanted to ask about some of the other comments on this page but I don't have enough rep points yet).