Problem 470715 · medium · Phase 04 Non-Linear Data Structures

Nth Number Built From Given Primes

heaps · number generation · multiple pointers · deduplication

Given a list primes of distinct primes in ascending order and an integer n, consider all positive integers whose prime factors all belong to primes. Counting 1 as the first such number, return the n-th one in increasing order.

Examples

Input:  primes = [2, 7, 13, 19], n = 12
Output: 32
Explanation: the sequence starts 1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32.

Input:  primes = [3, 5], n = 6
Output: 25
Explanation: 1, 3, 5, 9, 15, 25.

Constraints

  • 1 <= len(primes) <= 100, 2 <= primes[i] <= 1000, strictly increasing
  • 1 <= n <= 30000
  • Target complexity: O(n log p) where p = len(primes), using O(n + p) space.

Goals

  • Generalise a fixed-factor generator to an arbitrary list of primes
  • Keep one pointer per prime and a heap of the pending products
  • Skip duplicate products without a set
Starting Python…