Last Updated on June 17, 2022 by Ria Pathak

### 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:**

- We can find that by dividing
`p`

and`q`

by`r`

. `q/r`

gives total number of values divisible by`r`

in range [`1,q`

] ( or [`q,-1`

] if`q`

is negative).`p/r`

gives total number of values divisible by`r`

in range [`1,p`

] ( or [`p,-1`

] if`p`

is negative).- 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`

] ). - 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 NegativeAssuming 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]`

.

If range near to 0 is divisible byNOTE:`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 PositiveAssuming 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]`

.

If range near to 0 is divisible byNOTE:`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 PositiveAssuming 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