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 are given two sorted arrays and need to find the k-th smallest sum formed by adding one element from each array. Which approach guarantees an optimal solution in terms of time complexity for large input sizes?

easy

A. Use binary search on the sum range combined with a counting function to find how many pairs have sums less than or equal to mid.

B. Use dynamic programming to build a table of sums and select the k-th smallest.

C. Use a greedy approach by always picking the smallest available sum without revisiting pairs.

D. Generate all possible sums, sort them, and pick the k-th smallest sum.

Solution

1. Step 1: Understand problem constraints

   Brute force (generating all sums) is too slow for large inputs.

2. Step 2: Identify efficient approach

   Binary search on sum range with counting pairs ≤ mid efficiently narrows down the k-th smallest sum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search reduces search space logarithmically [OK]

Hint: Binary search on sums beats brute force for large inputs [OK]

Common Mistakes:

• Assuming greedy approach always works
• Using DP which is inefficient here

2. What is the time complexity of the optimal binary search on value range approach to find the median of K sorted arrays, each of average length N, with value range size M?

medium

A. O(K * log M * log N)

B. O(K * N * log M)

C. O(K * N * log N)

D. O(K * log N * log M)

Solution

1. Step 1: Analyze binary search outer loop

   Binary search on value range M takes O(log M) steps.

2. Step 2: Analyze counting elements ≤ mid

   Counting uses binary search on each array of length N, costing O(log N) per array, total O(K log N).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(K log M log N) [OK]

Hint: Counting uses binary search per array, not linear scan [OK]

Common Mistakes:

• Assuming linear scan over arrays (O(KN))
• Confusing N and M in complexity
• Ignoring binary search inside counting

3. The following code attempts to assign jobs to machines optimally. Which line contains a subtle bug that can cause incorrect scheduling?

medium

A. Line 5: Using enumerate without sorting jobs by start time.

B. Line 9: heapq.heapify(available) to initialize available machines heap.

C. Line 13: While loop condition to free machines before assignment.

D. Line 17: Calculating finish_time as start + duration.

Solution

1. Step 1: Identify the bug

   The code uses indexed_jobs = enumerate(jobs) without sorting jobs by start time, which breaks chronological processing.

2. Step 2: Consequences of missing sorting

   Without sorting, jobs may be assigned out of order, causing machines to be assigned incorrectly or appear busy when they should be free.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting jobs by start time is essential for correct scheduling [OK]

Hint: Jobs must be sorted by start time before assignment [OK]

Common Mistakes:

• Forgetting to sort jobs by start time
• Not freeing machines before assigning new jobs
• Incorrect finish time calculation

4. What is the time complexity of the optimal min-heap based algorithm for finding the smallest range covering k sorted lists, where N is the total number of elements across all lists and k is the number of lists?

medium

A. O(N log k) because each of the N elements is pushed and popped from a heap of size k.

B. O(k log N) because the heap size grows with total elements N and operations depend on k.

C. O(N * k) because each element is processed k times in the heap operations.

D. O(N) because each element is processed exactly once without extra overhead.

Solution

1. Step 1: Analyze heap operations

   Heap size is at most k since it stores one element from each list at a time.

2. Step 2: Count total operations

   Each of the N elements is pushed and popped exactly once, each heap operation costs O(log k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size k leads to O(log k) per operation, total N elements processed [OK]

Hint: Heap size k means log k per operation, total N elements [OK]

Common Mistakes:

• Assuming heap size grows with N, confusing log N vs log k
• Multiplying N by k incorrectly
• Ignoring heap operation cost

5. Suppose the array elements can be reused multiple times (duplicates allowed and repeated). Which modification to the k-sorted array sorting algorithm is necessary to correctly handle this scenario?

hard

A. No modification needed; the existing min-heap approach works correctly with duplicates.

B. Use a max-heap instead of a min-heap to handle duplicates correctly.

C. Add a frequency map to track counts and adjust heap operations accordingly.

D. Sort the array fully using a standard sort to handle duplicates reliably.

Solution

1. Step 1: Understand duplicates in k-sorted array

   Duplicates do not affect the heap property; min-heap handles equal elements correctly.

2. Step 2: Confirm no algorithmic change needed

   Heap operations remain valid; duplicates are naturally ordered by heapq.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap supports duplicates without extra data structures [OK]

Hint: Min-heap naturally supports duplicates without changes [OK]

Common Mistakes:

• Thinking max-heap is needed for duplicates
• Adding unnecessary frequency maps
• Defaulting to full sort unnecessarily