Recently, I was trying to find multiples of a number n in the range from a to b (both inclusive) in c++ For the problem: C – Anti Division. (I needed this approach for solving it.) Here is my approach:
-
Finding the multiples of n in range a to b (excluding both) by setting the answer to (b – a – 1) / n.
-
Setting answer to answer + 1 if a % n == 0 else to answer
-
Setting answer to answer + 1 if b % n == 0 else to answer
-
Printing the answer
It seems pretty right. But the problem is with this test: a = 4, b = 6, n = 5. The approach does this:
- Answer becomes to (b – a – 1) / n = (6 – 4 – 1) / 5 = 0
- Answer remains 0, since 4 is not divisible by 5.
- Answer remains 0, since 6 is not divisible by 5.
- The output is 0.
The result is 0, when the output should be 1, because in the range of 4 to 6, 5 comes, and hence the answer should be 1.
I also tried of thinking different approach to solve this, but I failed to think. Can anyone tell me any solution to this? Note that you can’t do brute force to solve this because the constraints for the input is as follows:
1 <= a, b, n <= 1000000000 (10 to the power 9)
// Code for the above approach
#include <bits/stdc++.h>
using namespace std;
int main(){
// Assigning the values as int
int a, b, n;
// Taking input
cin >> a >> b >> n;
// First step
int ans = (b - a - 1) / n;
// Second step
ans += ((a % n) == 0? 1: 0);
// Third step
ans += ((b % n) == 0? 1: 0);
// Last step
cout << ans;
}
>Solution :
I have to read the question several times to figure out that you are asking for the total numbers (counts) of multiples of n in the range [a,b], not the multiples themselves. The algorithm is pretty straightforward. Using integer division, b/n gives the number of multiples of n in the range [1,b], (a-1)/n gives the number of multiples of n in the range [1, a-1], so the difference gives the number of multiples of n in the range [a,b]. So the whole thing can be simplified to just
ans = b/n - (a-1)/n;