563. Nth Prime-Product Number
A toy factory makes gears from a list of allowed building-block sizes given in the array primes (the sizes are integers of at least 2; they may repeat and come in any order). A tooth count is valid if it equals 1 or can be written as a product of allowed sizes, where each size may be used any number of times, or not at all.
List all distinct valid tooth counts in increasing order, starting with 1. Return the n-th number of that list, or -1 if fewer than n valid counts are at most 2^31 - 1. Intermediate products can exceed 32 bits, so be careful with overflow.
Testing every integer is far too slow; aim for roughly O(n log k) time with k = primes.length, and O(n + k) space.
Example 1
- Input:
- n = 8, primes = [5,2]
- Output:
- 20
- Explanation:
The valid numbers are 1, 2, 4, 5, 8, 10, 16, 20, so the 8th is 20.
Example 2
- Input:
- n = 1, primes = [7,11]
- Output:
- 1
- Explanation:
The first valid number is always 1.
Example 3
- Input:
- n = 6, primes = [4,6]
- Output:
- 36
- Explanation:
Products of 4 and 6 give 1, 4, 6, 16, 24, 36 in increasing order, so the 6th is 36.
Constraints
- 1 ≤
n≤ 2 * 105 - 1 ≤
primes.length≤ 100 - 2 ≤
primes[i]≤ 1000 (not necessarily prime or distinct, in any order) - Only counts up to 231 - 1 are considered; if there are fewer than
nof them, return -1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log k)
- Space
- O(n + k)