Total numbers divisible by a number in a given range

Concepts Used:

Mathematics

Difficulty Level:

Hard

Problem Statement (Simplified):

For given three numbers r,p,q. We have to find the total number of values divisible by r in a range [p,q]. (Both Inclusive).

See original problem statement here

Test Case:

Input:
1
3 -10 30

Output:
14

Explaination:
There are total 14 numbers divisible by 3 in range [-10,30], that are [-9,-6,-3,0,3,6,9,12,15,18,21,24,27,30]

Solving Approach :

Bruteforce Approach:

1) We can start a loop from p to q, and then check if the current value is divisible by r or not, if yes, we increase the counter by 1.
2) After all numbers in a given range are iterated, we print the count.
3) This approach takes O(q-p) time complexity for a given range. But this approach is inefficient for larger ranges and a larger number of queries. So we move to a more efficient approach.

Efficient Approach:

1. We can find that by dividing p and q by r.
2. q/r gives total number of values divisible by r in range [1,q] ( or [ q,-1 ] if q is negative).
3. p/r gives total number of values divisible by r in range [1,p] ( or [ p,-1 ] if p is negative).
4. We can get our answer on subtracting number of values found in range [1,p] ( or [p,-1] ) from number of values found in range [1,q] ( or [q,-1] ).
5. An extra value should also be considered if following conditions are satisfied:
   a. If range contains 0, we would add an additional 1, as 0 is divisible by r but is not counted by above method.
   b.If p and q both values are positive and p is divisible by r.
   c. If p and q both values are negative and q is divisible by r.

Example:

We’ll take an example for different range cases :

Case 1: Negative to Negative

Assuming range as [-12,-2] and r=3, here gives -4 and gives 0, hence there are 4 numbers between range [-12,-1] i.e. [-12,-9,-6,-3]. Also there is no number in range [-2, -1], hence there are total 4 numbers which are divisible by ‘r’ in range [-12,-2].
NOTE: If range near to 0 is divisible by r, we add additional 1 to answer, that it is counted in both ranges i.e. [p,-1] and [q,-1] and on substraction, it is discarded, so we add an extra 1 in answer for it.

Case 2: Positive to Positive

Assuming range as [2,12] and r=3, here gives 0 and gives 4, hence there are 4 numbers between range [1,12] i.e. [3,6,9,12]. Also there is no number in range [1,2], hence there are total 4 numbers which are divisible by ‘r’ in range [2, 12].
NOTE: If range near to 0 is divisible by r, we add additional 1 to answer, that it is counted in both ranges i.e. [1,p] and [1,q] and on substraction, it is discarded, so we add an extra 1 in answer for it.

Case 3: Negative to Positive

Assuming range as [-12,12] and r=3, here gives -4 and gives 4, hence there are 4 numbers between range [-12, 1] i.e. [3,6,9,12]. Also there are 4 numbers in range [1,12]. Also, 0 is also divisible by 3, so it will be included as well as. Hence there are total 9 numbers which are divisible by ‘r’ in range [-12, 12].

Solutions:

#include <stdio.h>

long long count(long long r, long long p, long long q ){

  if((p>0 && p%r==0)|| (p==0 || q==0) || (q<0 && p<0 && q%r==0) ||( p<0 && q>0) )
    return (q/r)-(p/r)+1;
  else
    return (q/r)-(p/r);

}

int main()
{
  int test;
  scanf("%d", &test);

  while(test--){

    long long r, p, q;
    scanf("%lld%lld%lld",&r,&p,&q);

    printf("%lld\n",count(r,p,q));
  }
}

#include <bits/stdc++.h>
using namespace std;

long long count(long long r, long long p, long long q ){

  if((p>0 && p%r==0)|| (p==0 || q==0) || (q<0 && p<0 && q%r==0) ||( p<0 && q>0) )
    return (q/r)-(p/r)+1;
  else
    return (q/r)-(p/r);

}

int main()
{
  int test;
  cin>>test;

  while(test--){

    long r, p, q;
    cin>>r>>p>>q;

    cout<<count(r,p,q)<<endl; 
  }
}

import java.util.*;
import java.io.*;

public class Main {

  static long count(long r, long p, long q ){

    if((p>0 && p%r==0)|| (p==0 || q==0) || (q<0 && p<0 && q%r==0) ||( p<0 && q>0) )
      return (q/r)-(p/r)+1;
    else
      return (q/r)-(p/r);

  }


  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

      long r = sc.nextLong(), p = sc.nextLong(), q = sc.nextLong();

      System.out.println(count(r,p,q));
    }  

  }
}

[forminator_quiz id="819"]

This article tried to discuss the concept of Maths. Hope this blog helps you understand Total numbers divisible by a number in a given range. To practice more problems you can check out MYCODE|COMPETITIVE PROGRAMMING