Count Multiples in a Range

easy Programming Basics

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

Best approachTime O(1)Space O(1)

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).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. How many multiples of 3 are up to 10?
  2. Why do we use a - 1?