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 go through the best sites to learn programming languages and 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:

[TABS_R id=809]

[forminator_quiz id=”819″]

Previous post FRACTION1
Next post Find the missing number in sequence given as string

Leave a Reply

Your email address will not be published. Required fields are marked *