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

This can be done in O(1). Here you are a solution in C++.

auto first{ x % z == 0 ? x : x + z - x % z };
auto last{ y % z == 0 ? y : y - y % z };
auto ans{ (last - first) / z + 1 };

Where first is the first number that ∈ [x; y] and is divisible by z, last is the last number that ∈ [x; y] and is divisible by z and ans is the answer that you are looking for.

Answer 2

public static int Solution(int A, int B, int K) {

        int count = 0;

        //If A is divisible by K
        if(A % K == 0)
        {
            count = (B / K) - (A / K) + 1;
        }
        //If A is not divisible by K
        else if(A % K != 0)
        {
            count = (B / K) - (A / K);
        }

        return count;

}

Answer 3

Here is the solution to the problem written in Swift Programming Language.

Step 1: Find the first number in the range divisible by z.

Step 2: Find the last number in the range divisible by z.

Step 3: Use a mathematical formula to find the number of divisible numbers by z in the range.

func solution(_ x : Int, _ y : Int, _ z : Int) -> Int {
    var numberOfDivisible = 0

    var firstNumber: Int
    var lastNumber: Int

    if y == x {
        return x % z == 0 ? 1 : 0
    }
    
    //Find first number divisible by z
    let moduloX = x % z

    if moduloX == 0 {
        firstNumber = x
    } else {
        firstNumber = x + (z - moduloX)
    }

    //Fist last number divisible by z
    let moduloY = y % z
    if moduloY == 0 {
        lastNumber = y
    } else {
        lastNumber = y - moduloY
    }

    //Math formula
    numberOfDivisible = Int(floor(Double((lastNumber - firstNumber) / z))) + 1

    return numberOfDivisible
}

Answer 4

here n will give you count of number and will print sum of all numbers that are divisible by k

int a = sc.nextInt();
int b = sc.nextInt();
int k = sc.nextInt();
int first = 0;

if (a > k) {
  first = a + a/k;
} else {
  first = k;
}

int last = b - b%k;

if (first > last) {
  System.out.println(0);
} else {
  int n = (last - first)/k+1;
  System.out.println(n * (first + last)/2);
}

Answer 5

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 :)

1. 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

2. 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

3. 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 :)

Answer 6

^{(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

Answer 7

The time complexity of the solution will be linear.

Code Snippet :

int countDiv(int a, int b, int m)
{
    int mod = (min(a, b)%m==0);
    int cnt  = abs(floor(b/m) - floor(a/m))  +  mod;
    return cnt;
}

Answer 8

Let [A;B] be an interval of positive integers including A and B such that 0 <= A <= B, K be the divisor.

It is easy to see that there are N(A) = ⌊A / K⌋ = floor(A / K) factors of K in interval [0;A]:

         1K       2K       3K       4K       5K
●········x········x··●·····x········x········x···>
0                    A

Similarly, there are N(B) = ⌊B / K⌋ = floor(B / K) factors of K in interval [0;B]:

         1K       2K       3K       4K       5K
●········x········x········x········x···●····x···>
0                                       B

Then N = N(B) - N(A) equals to the number of K's (the number of integers divisible by K) in range (A;B]. The point A is not included, because the subtracted N(A) includes this point. Therefore, the result should be incremented by one, if A mod K is zero:

N := N(B) - N(A)

if (A mod K = 0)
  N := N + 1

Implementation in PHP

function solution($A, $B, $K) {
  if ($K < 1)
    return 0;

  $c = floor($B / $K) - floor($A / $K);

  if ($A % $K == 0)
    $c++;

  return (int)$c;
}

In PHP, the effect of the floor function can be achieved by casting to the integer type:

$c = (int)($B / $K) - (int)($A / $K);

which, I think, is faster.

Answer 9

Division (a/b=c) by definition - taking a set of size a and forming groups of size b. The number of groups of this size that can be formed, c, is the quotient of a and b. - is nothing more than the number of integers within range/interval ]0..a] (not including zero, but including a) that are divisible by b.

so by definition:
Y/Z - number of integers within ]0..Y] that are divisible by Z
and
X/Z - number of integers within ]0..X] that are divisible by Z

thus:
result = [Y/Z] - [X/Z] + x (where x = 1 if and only if X is divisible by Y otherwise 0 - assuming the given range [X..Y] includes X)

example :
for (6, 12, 2) we have 12/2 - 6/2 + 1 (as 6%2 == 0) = 6 - 3 + 1 = 4 // {6, 8, 10, 12}
for (5, 12, 2) we have 12/2 - 5/2 + 0 (as 5%2 != 0) = 6 - 2 + 0 = 4 // {6, 8, 10, 12}

Answer 10

Here is my short and simple solution in C++ which got 100/100 on codility. :) Runs in O(1) time. I hope its not difficult to understand.

int solution(int A, int B, int K) {
    // write your code in C++11
    int cnt=0;
    if( A%K==0 or B%K==0)
        cnt++;
    if(A>=K)
        cnt+= (B - A)/K;
    else
        cnt+=B/K;

    return cnt;
}

Answer 11

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).

Answer 12

(floor)(high/d) - (floor)(low/d) - (high%d==0)

Explanation:

There are a/d numbers divisible by d from 0.0 to a. (d!=0)

Therefore (floor)(high/d) - (floor)(low/d) will give numbers divisible in the range (low,high] (Note that low is excluded and high is included in this range)

Now to remove high from the range just subtract (high%d==0)

Works for integers, floats or whatever (Use fmodf function for floats)

Answer 13

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;

Answer 14

Divide y-x by z, rounding down. Add one if y%z < x%z or if x%z == 0.

No mathematical proof, unless someone cares to provide one, but test cases, in Perl:

#!perl
use strict;
use warnings;
use Test::More;

sub multiples_in_range {
  my ($x, $y, $z) = @_;
  return 0 if $x > $y;
  my $ret = int( ($y - $x) / $z);
  $ret++ if $y%$z < $x%$z or $x%$z == 0;
  return $ret;
}   

for my $z (2 .. 10) {
  for my $x (0 .. 2*$z) {
    for my $y (0 .. 4*$z) {
      is multiples_in_range($x, $y, $z),
         scalar(grep { $_ % $z == 0 } $x..$y),
         "[$x..$y] mod $z";
    }
  }
}

done_testing;

Output:

$ prove divrange.pl 
divrange.pl .. ok      
All tests successful.
Files=1, Tests=3405,  0 wallclock secs ( 0.20 usr  0.02 sys +  0.26 cusr  0.01 csys =  0.49 CPU)
Result: PASS

Answer 15

Won't strive for an o(1) solution, this leave for more clever person:) Just feel this is a perfect usage scenario for function programming. Simple and straightforward.

 > x,y,z=1,1000,6
 => [1, 1000, 6] 
 > (x..y).select {|n| n%z==0}.size
 => 166 

EDIT: after reading other's O(1) solution. I feel shamed. Programming made people lazy to think...