Super Ugly Number
Medium · 1-D Dynamic Programming · Explanation and code example
Merge Prime-Multiple Streams
How it works
Generalize ugly-number generation to the supplied primes. Each prime points into the previously generated sequence and proposes its next multiple. Append the minimum proposal and advance every tied stream, preserving sorted order without duplicate numbers.
Steps
- Start with one and one index per prime.
- Compute each prime times its indexed sequence value.
- Append the minimum and advance all matching indices.
Complexity
- Time: O(nk), for n generated numbers and k primes.
- Space: O(n + k).
Things to watch for
- Advance all tied prime streams.
- One is included even though it has no prime factors.
- Use a sufficiently wide multiplication type in C++.
Python code example
class Solution:
def nthSuperUglyNumber(self, n: int, primes: list[int]) -> int:
k = len(primes)
nums = [1]
indices = [0] * k
while len(nums) < n:
nexts = [0] * k
for i in range(k):
nexts[i] = nums[indices[i]] * primes[i]
next = min(nexts)
for i in range(k):
if next == nexts[i]:
indices[i] += 1
nums.append(next)
return nums[-1]
C++ code example
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
const int k = primes.size();
vector<int> indices(k);
vector<long long> uglyNums{1};
while (uglyNums.size() < n) {
vector<long long> nexts(k);
for (int i = 0; i < k; ++i)
nexts[i] = uglyNums[indices[i]] * primes[i];
const long long next = ranges::min(nexts);
for (int i = 0; i < k; ++i)
if (next == nexts[i])
++indices[i];
uglyNums.push_back(next);
}
return uglyNums.back();
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.