Count Multiples in a Range
Problem
Count the whole numbers from a to b (both included) that can be divided by m with no remainder. Input: a, b and m with 1 <= a <= b.
Constraints
- 1 <= a <= b <= 200000
- 1 <= m <= 10^9
Examples
Input
1 10 3
Output
3
Solutions
The count of multiples of m up to x is x / m (rounded down). Subtracting the count before a leaves the ones inside the range. O(1).
/*
* Problem : Count multiples.
* Input : a, b and m.
* Output : The count.
* Approach: Formula.
* Time : O(1)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static long solve(long a, long b, long m) {
// Step 1: Up to x there are x / m multiples of m. The multiples inside [a, b] are those up to b minus those before a.
return b / m - (a - 1) / m;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
long m = scanner.nextLong();
System.out.println(solve(a, b, m));
}
}
Hints (2)
- How many multiples of 3 are up to 10?
- Why do we use a - 1?