373. Nth Divisible by Any
A game show calls out positive whole numbers in increasing order, and a number is a winner if it is divisible by at least one of three given numbers a, b and c. The host wants to know which number is the n-th winner.
Given n, a, b and c, return the n-th positive integer that is divisible by a, b or c. The answer is guaranteed to fit in a 32-bit signed integer. Counting winners one by one is too slow, so count how many winners are at most a value x in constant time and search for the right x.
Example 1
- Input:
- n = 4a = 2b = 3c = 7
- Output:
- 6
- Explanation:
The winners are 2, 3, 4, 6, 7, 8, ... and the 4th is 6.
Example 2
- Input:
- n = 3a = 4b = 6c = 9
- Output:
- 8
- Explanation:
The winners are 4, 6, 8, 9, 12, ... and the 3rd is 8.
Constraints
1 ≤ n ≤ 109
1 ≤ a, b, c ≤ 105
The answer fits in a signed 32-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log(n * min(a, b, c)))
- Space
- O(1)