N-th Number Built From Primes
MediumHeap / Priority Queue
Problem
Given a list of distinct prime numbers primes, consider every positive integer whose prime factors all belong to primes. The number 1 is included, since it has no prime factors at all.
List these integers in increasing order and return the n-th one (1-indexed).
Example 1
- Input:
- primes = [2, 3, 5], n = 10
- Output:
- 12
The sequence starts 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. 7 and 11 are skipped because they are other primes.
Example 2
- Input:
- primes = [3, 7], n = 5
- Output:
- 21
1, 3, 7, 9, 21.
Example 3
- Input:
- primes = [2], n = 1
- Output:
- 1
Constraints
- 1 ≤ primes.length ≤ 20
- 2 ≤ primes[i] ≤ 100, all distinct primes
- 1 ≤ n ≤ 2000
- The answer is at most 10^12.
Hint
Show the first hint
Testing every integer for its factors wastes time on numbers that are not in the sequence. Can you generate only members instead?
Walkthrough
How to approach it
01Clarify before coding
- Is 1 part of the sequence? Yes, it is the 1st element.
- Can the same number be produced in different ways? Yes, 6 = 2·3 = 3·2, so duplicates must be filtered.
- How large can values get? Up to 10^12, which fits in a JavaScript number exactly.
02Brute force
Test 1, 2, 3, ... one by one, dividing out every allowed prime, and count those that reduce to 1.
Cost: Proportional to the VALUE of the answer, not to n: with primes [97] the 20th member is about 10^38. Hopeless for sparse prime sets.
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.