Super Ugly Number (K Primes)

📋

Problem

Imagine you want to generate numbers whose prime factors come only from a given set of primes, like creating special 'super ugly' numbers for cryptographic or mathematical applications.

Given an integer n and an array of k primes primes, return the nth super ugly number. A super ugly number is a positive integer whose prime factors are in the array primes. The sequence starts with 1 as the first super ugly number.

1 ≤ n ≤ 10^51 ≤ k ≤ 1002 ≤ primes[i] ≤ 1000primes is sorted in ascending order and contains unique primes

Edge cases: n = 1, primes = [2] → output 1 (smallest super ugly number)primes contains only one prime, e.g., [3] → output is powers of 3n is large (e.g., 10^5) with multiple primes → tests efficiency

</>

IDE

def nthSuperUglyNumber(n: int, primes: list[int]) -> int:public int nthSuperUglyNumber(int n, int[] primes)int nthSuperUglyNumber(int n, vector<int>& primes)function nthSuperUglyNumber(n, primes)

def nthSuperUglyNumber(n, primes):
    # Write your solution here
    pass

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int nthSuperUglyNumber(int n, vector<int>& primes) {
    // Write your solution here
    return 0;
}

function nthSuperUglyNumber(n, primes) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong nth number due to duplicates or missing numbersNot advancing pointers correctly when multiple primes generate the same next ugly number✅ Advance all pointers i where dp[pointers[i]] * primes[i] == next_ugly_number

Wrong: Output other than 1 for n=1Missing base case handling for n=1✅ Return 1 immediately if n == 1

Wrong: Sequence missing repeated prime multiplesConfusing 0/1 knapsack with unbounded usage of primes✅ Allow multiple uses of the same prime by not restricting pointer increments to once per prime

Wrong: Off-by-one error in indexing dp arrayReturning dp[n] instead of dp[n-1]✅ Return dp[n-1] as the nth super ugly number

Wrong: Timeout or no output for large inputsUsing brute force or O(n^2) approach instead of O(n log k)✅ Implement min-heap based k-way merge to achieve O(n log k) time

✓

Test Cases

Focus on handling smallest inputs and single prime arrays correctly.

Watch out for common algorithmic pitfalls like greedy mistakes and pointer mismanagement.

Optimize your solution to use a min-heap for efficient merging of prime multiples.

t1_01basic

Input{"n":12,"primes":[2,7,13,19]}

Expected32

⏱ Performance - must finish in 2000ms

The sequence is [1,2,4,7,8,13,14,16,19,26,28,32], so the 12th super ugly number is 32.

💡 Think about merging multiple sorted sequences generated by multiplying primes.

💡 Use a min-heap to efficiently get the next smallest candidate from all prime multiples.

💡 Maintain pointers for each prime to track the next multiple to consider.

Why it failed: Incorrect output means the merging or pointer update logic is wrong. Fix by ensuring each prime's pointer advances only when its multiple is chosen.

✓ Correctly merges prime multiples and updates pointers.

t1_02basic

Input{"n":5,"primes":[2,3,5]}

Expected5

⏱ Performance - must finish in 2000ms

The sequence is [1,2,3,4,5], so the 5th super ugly number is 5.

💡 Start from 1 and generate next numbers by multiplying primes.

💡 Track indices for each prime to avoid duplicates and maintain order.

💡 Use dp array and update dp[i] = min of all prime multiples at their pointers.

Why it failed: If output is wrong, likely duplicates or ordering errors. Fix by advancing pointers only when their multiple equals the chosen next number.

✓ Correctly generates sequence with proper pointer advancement.

t2_01edge

Input{"n":1,"primes":[2]}

Expected1

⏱ Performance - must finish in 2000ms

The first super ugly number is always 1 regardless of primes.

💡 Remember the sequence starts with 1 by definition.

💡 Check if your code handles n=1 as a base case.

💡 Return 1 immediately when n=1 without further computation.

Why it failed: Output not 1 means base case for n=1 missing. Fix by returning 1 directly when n=1.

✓ Correctly handles base case n=1.

t2_02edge

Input{"n":4,"primes":[3]}

Expected27

⏱ Performance - must finish in 2000ms

Sequence with single prime 3 is [1,3,9,27], so 4th is 27.

💡 With one prime, sequence is powers of that prime starting at 1.

💡 Ensure your code handles single prime arrays correctly.

💡 Use pointer and dp array to generate powers without skipping.

Why it failed: Wrong output means single prime logic flawed. Fix by correctly updating pointer and dp for single prime multiples.

✓ Correctly generates powers for single prime.

t2_03edge

Input{"n":10,"primes":[2,3,5,7,11,13,17,19,23,29]}

Expected10

⏱ Performance - must finish in 2000ms

The 10th super ugly number with these primes is 20 (sequence starts 1,2,3,4,5,6,7,8,9,10, ... but filtered by primes).

💡 Test boundary with maximum k=10 primes.

💡 Check if your code scales with multiple primes without errors.

💡 Verify min-heap or pointer updates handle all primes correctly.

Why it failed: Incorrect output means pointer or heap logic fails with many primes. Fix by ensuring all primes are processed and pointers updated properly.

✓ Handles multiple primes at boundary correctly.

t3_01corner

Input{"n":15,"primes":[2,3,5]}

Expected24

⏱ Performance - must finish in 2000ms

The 15th super ugly number with primes [2,3,5] is 24.

💡 Beware of greedy approach picking next number without considering all primes.

💡 Use dynamic programming or heap to merge sequences properly.

💡 Advance pointers only when their multiple equals the chosen next number.

Why it failed: Greedy approach fails by picking local min without merging all sequences. Fix by using min-heap or dp with pointers.

✓ Correctly avoids greedy trap by merging all sequences.

t3_02corner

Input{"n":7,"primes":[7,11]}

Expected343

⏱ Performance - must finish in 2000ms

Sequence is powers of 7 and 11 combined; 7th super ugly number is 7^3=343.

💡 Check if your code confuses 0/1 knapsack style with unbounded multiples.

💡 Each prime can be used unlimited times, so powers grow exponentially.

💡 Ensure pointers advance correctly for repeated prime multiples.

Why it failed: Confusing 0/1 with unbounded leads to missing repeated prime multiples. Fix by allowing multiple uses of the same prime.

✓ Correctly handles unbounded prime multiples.

t3_03corner

Input{"n":9,"primes":[2,3,5]}

Expected10

⏱ Performance - must finish in 2000ms

The 9th super ugly number is 12, sequence: 1,2,3,4,5,6,8,9,12.

💡 Watch out for off-by-one errors in indexing dp array.

💡 Ensure dp array size matches n and indices start correctly.

💡 Return dp[n-1] as nth super ugly number.

Why it failed: Off-by-one error causes wrong output index. Fix by returning dp[n-1] not dp[n].

✓ Correct indexing yields correct nth number.

t4_01performance

Input{"n":100000,"primes":[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100000 and k=100 primes tests O(n log k) complexity within 2 seconds.

💡 Use a min-heap to merge k sequences efficiently.

💡 Avoid brute force or O(n^2) approaches.

💡 Optimize pointer updates and heap operations.

Why it failed: TLE indicates brute force or inefficient approach. Fix by implementing O(n log k) min-heap based solution.

✓ Efficient O(n log k) solution passes performance test.

Practice

1. You have K identical machines and a list of jobs, each with a start time and duration. You want to assign each job to a machine so that each machine processes jobs sequentially without overlap, always choosing the earliest available machine with the smallest index. Which algorithmic approach guarantees an optimal assignment minimizing waiting times and correctly handles job scheduling in chronological order?

easy

A. Greedy approach that assigns each job to the first machine found free by scanning all machines linearly.

B. Use a min-heap to track available machines by their next free time and assign jobs in order of start time, updating machine availability accordingly.

C. Dynamic programming that tries all possible assignments and picks the minimum total completion time.

D. Sort jobs by duration and assign them to machines in that order to minimize total processing time.

Solution

1. Step 1: Understand the problem constraints

   The problem requires assigning jobs to machines so that each job starts no earlier than its start time, machines process jobs sequentially, and the earliest available machine with the smallest index is chosen.

2. Step 2: Identify the correct approach

   Using a min-heap to track machine availability by next free time allows efficient retrieval of the earliest available machine. Sorting jobs by start time ensures chronological processing. This approach guarantees optimal scheduling and respects machine indices.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap + sorting jobs by start time -> optimal scheduling [OK]

Hint: Min-heap tracks earliest available machine efficiently [OK]

Common Mistakes:

• Using linear search for machine availability leads to O(nK) time
• Sorting by duration ignores job start times and causes conflicts
• DP approach is infeasible due to large state space

2. You need to generate the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently merges multiple sorted sequences generated by multiplying previously found numbers by these primes?

easy

A. Use a min-heap to merge multiple sorted sequences generated by multiplying known ugly numbers by 2, 3, and 5, while avoiding duplicates.

B. Use a greedy approach that picks the smallest next candidate without tracking duplicates or previously generated numbers.

C. Use a brute force check for each number to test if it only has 2, 3, and 5 as prime factors.

D. Use a dynamic programming approach with three pointers to merge sequences but without a heap.

Solution

1. Step 1: Understand the problem structure

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, which can be seen as merging three sorted sequences: multiples of 2, 3, and 5 of previously found ugly numbers.

2. Step 2: Identify the optimal merging technique

   A min-heap efficiently merges these sequences by always extracting the smallest next candidate and avoids duplicates by tracking seen numbers, ensuring optimal time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap merges k sorted sequences optimally [OK]

Hint: Min-heap merges multiple sorted sequences efficiently [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Ignoring duplicates in merging
• Using greedy without tracking duplicates

3. Consider the following buggy code for finding the k-th smallest sum of pairs from two sorted arrays. Which line contains the subtle bug that can cause incorrect results or runtime errors?

def countPairs(nums1, nums2, mid):
    count = 0
    j = len(nums2) - 1
    for i in range(len(nums1)):
        while j >= 0 and nums1[i] + nums2[j] > mid:
            j -= 1
        count += (j + 1)
    return count

def kthSmallestSum(nums1, nums2, k):
    low = nums1[0] + nums2[0]
    high = nums1[-1] + nums2[-1]
    while low < high:
        mid = (low + high) // 2
        if countPairs(nums1, nums2, mid) <= k:  # Bug here
            low = mid + 1
        else:
            high = mid
    return low

medium

A. Line with 'j = len(nums2) - 1' initialization

B. Line with 'count += (j + 1)' inside countPairs

C. Line with 'while j >= 0 and nums1[i] + nums2[j] > mid:' condition

D. Line with 'if countPairs(nums1, nums2, mid) <= k:' in kthSmallestSum

Solution

1. Step 1: Understand binary search condition

   Correct condition is countPairs(...) < k to move low up; using ≤ k skips valid sums.

2. Step 2: Effect of bug

   Using ≤ k causes binary search to overshoot and miss the exact k-th sum, returning incorrect result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing ≤ to < fixes correctness [OK]

Hint: Binary search must use strict less-than for correct convergence [OK]

Common Mistakes:

• Using ≤ instead of < in binary search condition
• Off-by-one errors in countPairs

4. What is the time complexity of the divide and conquer approach to merge k sorted arrays with a total of N elements?

medium

A. O(N log N) because each merge sorts the combined arrays

B. O(N log k) because merging pairs reduces arrays by half each iteration

C. O(k N) because each of the k arrays is merged sequentially

D. O(N k) because each element is compared with k arrays

Solution

1. Step 1: Identify number of merge rounds

   Divide and conquer merges pairs of arrays, halving the number of arrays each round, so log k rounds.

2. Step 2: Calculate work per round

   Each round merges all N elements once, so O(N) per round.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   O(N) work per round x log k rounds -> O(N log k) [OK]

Hint: Divide and conquer halves arrays each round -> log k rounds [OK]

Common Mistakes:

• Confusing total elements N with number of arrays k
• Assuming sorting entire array each time
• Multiplying N by k incorrectly

5. The following code attempts to sort a k-sorted array using a min-heap. Identify the bug that causes incorrect or incomplete output.

medium

A. Line initializing the heap with arr[:k+1] is incorrect; should be arr[:k].

B. The for-loop range should be from 0 to len(arr), not k+1 to len(arr).

C. Using heapq.heappush instead of heappop in the loop causes wrong heap operations.

D. The code does not extract remaining elements from the heap after the for-loop.

Solution

1. Step 1: Analyze heap initialization and loop

   Heap is correctly initialized with first k+1 elements; loop pushes and pops correctly.

2. Step 2: Check for extraction after loop

   After the loop, remaining elements in heap are not popped and placed back into arr, causing incomplete output.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing final extraction leads to missing sorted elements [OK]

Hint: Always pop remaining heap elements after main loop [OK]

Common Mistakes:

• Forgetting to pop leftover heap elements
• Incorrect heap size initialization
• Misusing heap push/pop functions