Sum of Multiples Below n
Problem
Read n, a and b. Add all the whole numbers below n (from 1 to n - 1) that are a multiple of a or a multiple of b. A number that is a multiple of both is added only once. Print the sum.
Constraints
- 1 <= n <= 10^6
- 1 <= a, b <= 1000
Examples
Input
10 3 5
Output
23
Solutions
Adding the sum of multiples of a and the sum of multiples of b would count common multiples twice. The loop with or avoids this. For huge n a formula (sum of multiples of a, plus of b, minus of lcm(a, b)) is faster than a loop.
/*
* Problem : Sum the multiples.
* Input : n, a and b.
* Output : The sum.
* Approach: Loop with a condition.
* Time : O(n)
* 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: Go through every number from 1 up to n - 1.
long total = 0;
for (long value = 1; value < a; value++) {
// Step 2: One if with "or" adds a number only once, even if it is a multiple of both.
if (value % b == 0 || value % m == 0) {
total += value;
}
}
return total;
}
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 (1)
- Which numbers would be counted twice with two separate loops?