Divisible by Any of Three
MediumMath & Geometry
Problem
Three warning lights blink every a, b and c seconds, all starting at second 0. Over seconds 1..n, count the seconds in which at least one light blinks.
Equivalently, return how many integers in [1, n] are divisible by a, by b or by c.
Example 1
- Input:
- n = 10, a = 2, b = 3, c = 5
- Output:
- 8
2, 3, 4, 5, 6, 8, 9 and 10; only 1 and 7 are missed.
Example 2
- Input:
- n = 15, a = 4, b = 6, c = 9
- Output:
- 5
4, 6, 8, 9 and 12. Note that 12 is counted once.
Example 3
- Input:
- n = 12, a = 6, b = 6, c = 6
- Output:
- 2
Constraints
- 0 ≤ n ≤ 10^15
- 1 ≤ a, b, c ≤ 10^9
Hint
Show the first hint
⌊n / a⌋ numbers in [1, n] are multiples of a. Adding the three counts double-counts something.
Walkthrough
How to approach it
01Clarify before coding
- Can a, b, c be equal or divide each other? Yes; inclusion-exclusion handles it automatically.
- Can n be 0? Yes, the answer is then 0.
- Do intermediate values fit? lcm(a, b, c) can be about 10^27, beyond 64-bit and far beyond JavaScript's 2^53, so it must be capped.
02Brute force
Loop over 1..n and test divisibility by each of a, b, c.
Cost: O(n): 10^15 iterations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.