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

Question

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 ?

Answer 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;