The n-th number divisible by a or b
Find the n-th number that is a multiple of a or b without listing them, by searching the value and counting with inclusion and exclusion. About 16 minutes.
Counting without listing
Take the numbers that are multiples of 2 or of 3: 2, 3, 4, 6, 8, 9, 10, 12 and so on. What is the 5th one? For small n you can just list them. But what if n is a billion?
The trick is to count instead of list. Up to a value x there are x divided by 2, rounded down, even numbers, and x divided by 3 multiples of 3. Add them. But a number like 6 is a multiple of both, so it was counted twice, and you must take away one count of the numbers divisible by 6, the smallest number that both divide.
threes = 20 // 3 # 6 fours = 20 // 4 # 5 both = 20 // 12 # 1 total = 6 + 5 - 1
The 4th one is at most 4 × 3 = 12. Try the middle, 6: the count up to 6 is 2 + 1 − 0 = 3. That is fewer than 4, so look higher.
Then halve the values
The count up to x never decreases as x grows, so the n-th qualifying number is the smallest x whose count reaches n. Search between 1 and n times the smaller of a and b, since the multiples of that smaller number alone already reach n.
Be careful with the size of the numbers. The answer can be tens of trillions, which needs a 64-bit number, even though the problem may ask for it modulo something at the end.
low, high = 1, 1000
while low < high:
mid = (low + high) // 2
if mid // 3 >= 7:
high = mid
else:
low = mid + 1Up to 30, how many numbers are divisible by 4 or 6? (The least common multiple of 4 and 6 is 12.)
- A10, which is 7 + 5 − 2
- B12, which is 7 + 5
- C8
Show the answer
10, which is 7 + 5 − 2. 30 divided by 4 is 7, by 6 is 5, and by 12 is 2 (rounded down).
The n-th multiple of a or b
Consider the positive whole numbers that are divisible by a or by b (or both), in increasing order. Return the n-th of them, modulo 1,000,000,007.
n = 5, a = 2, b = 3 → 8
1 ≤ n ≤ 1,000,000,000 · 2 ≤ a, b ≤ 40,000