Super Ugly Number (K Primes)

🎯

Super Ugly Number (K Primes)

mediumHEAPAmazonGoogle

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.

💡 This problem is about generating a sequence of numbers with restricted prime factors. Beginners often struggle because naive methods lead to huge computations or duplicates, and understanding how to efficiently merge multiple sequences is key.

📋

Problem Statement

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

💡

Example

Input"n = 12, primes = [2,7,13,19]"

Output32

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

• n = 1, primes = [2] → output 1 (smallest super ugly number)
• primes contains only one prime, e.g., [3] → output is powers of 3
• n is large (e.g., 10^5) with multiple primes → tests efficiency
• primes contains large primes close to 1000 → tests handling large factors

⚠️

Common Mistakes

Not handling duplicates when multiple primes generate the same number

Sequence contains duplicates, leading to incorrect nth number

✅ Increment all pointers or skip duplicates in heap approach when the same number appears multiple times

Using brute force approach for large n leading to TLE

Code times out or runs too slowly

✅ Use pointer or heap-based optimized approaches

Integer overflow when multiplying primes and ugly numbers

Runtime errors or incorrect results

✅ Use long/int64 types or check for overflow before multiplication

Incorrect initialization of pointers or heap elements

Wrong sequence generation or runtime errors

✅ Initialize pointers to zero and heap with first multiples correctly

Not returning 1 as the first super ugly number

Sequence starts incorrectly, failing base case

✅ Always start sequence with 1 as the first super ugly number

🧠

Brute Force (Generate and Check Multiples)

💡 This approach exists to understand the problem from first principles by generating candidates and checking if they qualify, though it is inefficient and impractical for large inputs.

Intuition

Start from 1 and repeatedly multiply by each prime to generate candidates, then pick the smallest new candidate each time to build the sequence.

Algorithm

1. Initialize a list with the first super ugly number 1.
2. For each new number to generate, multiply all previously found super ugly numbers by each prime to generate candidates.
3. Select the smallest candidate that is greater than the last added number and not already in the list.
4. Repeat until the nth super ugly number is found.

💡 This algorithm is conceptually simple but hard to implement efficiently because it generates many duplicates and requires checking for uniqueness.

</>

Code

def nthSuperUglyNumber(n, primes):
    ugly = [1]
    seen = set(ugly)
    while len(ugly) < n:
        candidates = []
        for p in primes:
            for u in ugly:
                val = p * u
                if val not in seen:
                    candidates.append(val)
        next_ugly = min(candidates)
        ugly.append(next_ugly)
        seen.add(next_ugly)
    return ugly[-1]

# Driver code
if __name__ == '__main__':
    print(nthSuperUglyNumber(12, [2,7,13,19]))  # Output: 32

Line Notes

ugly = [1]Initialize the sequence with the first super ugly number 1

seen = set(ugly)Keep track of numbers already generated to avoid duplicates

for p in primes:Iterate over each prime to generate multiples

for u in ugly:Multiply each prime by all previously found super ugly numbers

if val not in seen:Avoid adding duplicates to candidates

next_ugly = min(candidates)Select the smallest candidate as the next super ugly number

ugly.append(next_ugly)Add the next super ugly number to the sequence

return ugly[-1]Return the nth super ugly number

import java.util.*;
public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        List<Integer> ugly = new ArrayList<>();
        ugly.add(1);
        Set<Integer> seen = new HashSet<>();
        seen.add(1);
        while (ugly.size() < n) {
            List<Integer> candidates = new ArrayList<>();
            for (int p : primes) {
                for (int u : ugly) {
                    long val = (long)p * u;
                    if (val <= Integer.MAX_VALUE && !seen.contains((int)val)) {
                        candidates.add((int)val);
                    }
                }
            }
            int nextUgly = Collections.min(candidates);
            ugly.add(nextUgly);
            seen.add(nextUgly);
        }
        return ugly.get(n - 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.nthSuperUglyNumber(12, new int[]{2,7,13,19})); // 32
    }
}

Line Notes

List<Integer> ugly = new ArrayList<>();Initialize list to store super ugly numbers

ugly.add(1);Add the first super ugly number

Set<Integer> seen = new HashSet<>();Track generated numbers to avoid duplicates

for (int p : primes)Iterate over each prime

for (int u : ugly)Multiply prime by all previously found super ugly numbers

if (val <= Integer.MAX_VALUE && !seen.contains((int)val))Check for duplicates and integer overflow

int nextUgly = Collections.min(candidates);Find smallest candidate for next super ugly number

return ugly.get(n - 1);Return nth super ugly number

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int nthSuperUglyNumber(int n, vector<int>& primes) {
    vector<int> ugly = {1};
    set<int> seen = {1};
    while ((int)ugly.size() < n) {
        vector<int> candidates;
        for (int p : primes) {
            for (int u : ugly) {
                long long val = (long long)p * u;
                if (val <= INT_MAX && seen.find((int)val) == seen.end()) {
                    candidates.push_back((int)val);
                }
            }
        }
        int nextUgly = *min_element(candidates.begin(), candidates.end());
        ugly.push_back(nextUgly);
        seen.insert(nextUgly);
    }
    return ugly.back();
}

int main() {
    vector<int> primes = {2,7,13,19};
    cout << nthSuperUglyNumber(12, primes) << endl; // 32
    return 0;
}

Line Notes

vector<int> ugly = {1};Initialize vector with first super ugly number

set<int> seen = {1};Use set to track duplicates

for (int p : primes)Loop over each prime

for (int u : ugly)Multiply prime by all previously found super ugly numbers

if (val <= INT_MAX && seen.find((int)val) == seen.end())Avoid duplicates and overflow

int nextUgly = *min_element(candidates.begin(), candidates.end());Find smallest candidate

ugly.push_back(nextUgly);Add next super ugly number

return ugly.back();Return nth super ugly number

function nthSuperUglyNumber(n, primes) {
    const ugly = [1];
    const seen = new Set(ugly);
    while (ugly.length < n) {
        const candidates = [];
        for (const p of primes) {
            for (const u of ugly) {
                const val = p * u;
                if (!seen.has(val)) {
                    candidates.push(val);
                }
            }
        }
        const nextUgly = Math.min(...candidates);
        ugly.push(nextUgly);
        seen.add(nextUgly);
    }
    return ugly[ugly.length - 1];
}

// Test
console.log(nthSuperUglyNumber(12, [2,7,13,19])); // 32

Line Notes

const ugly = [1];Initialize array with first super ugly number

const seen = new Set(ugly);Track generated numbers to avoid duplicates

for (const p of primes)Iterate over each prime

for (const u of ugly)Multiply prime by all previously found super ugly numbers

if (!seen.has(val))Avoid duplicates

const nextUgly = Math.min(...candidates);Select smallest candidate

ugly.push(nextUgly);Add next super ugly number

return ugly[ugly.length - 1];Return nth super ugly number

⏱

Complexity

TimeO(n^2 * k)

SpaceO(n^2)

For each of the n numbers, we generate up to n*k candidates by multiplying all previous numbers by each prime, leading to quadratic time and space.

💡 For n=20 and k=4, this means roughly 1600 operations per iteration, which quickly becomes infeasible for large n.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Better Approach (Pointers for Each Prime)

💡 This approach improves efficiency by maintaining pointers for each prime to track which super ugly number to multiply next, avoiding duplicate generation and reducing complexity.

Intuition

Instead of generating all multiples, keep track of the next multiple for each prime using pointers, and pick the minimum among them to build the sequence.

Algorithm

1. Initialize an array ugly with 1 as the first super ugly number.
2. Create an array pointers of size k, all initialized to 0, to track indices for each prime.
3. For each iteration, compute candidates by multiplying primes[i] with ugly[pointers[i]].
4. Select the minimum candidate as the next super ugly number and increment pointers for all primes that generated this minimum.
5. Repeat until the nth super ugly number is found.

💡 This algorithm cleverly merges k sorted sequences of multiples by using pointers, avoiding duplicates and unnecessary computations.

</>

Code

def nthSuperUglyNumber(n, primes):
    k = len(primes)
    ugly = [1] * n
    pointers = [0] * k
    for i in range(1, n):
        candidates = [primes[j] * ugly[pointers[j]] for j in range(k)]
        next_ugly = min(candidates)
        ugly[i] = next_ugly
        for j in range(k):
            if candidates[j] == next_ugly:
                pointers[j] += 1
    return ugly[-1]

# Driver code
if __name__ == '__main__':
    print(nthSuperUglyNumber(12, [2,7,13,19]))  # Output: 32

Line Notes

k = len(primes)Number of primes to track

ugly = [1] * nInitialize list to store super ugly numbers

pointers = [0] * kInitialize pointers for each prime's multiple

candidates = [primes[j] * ugly[pointers[j]] for j in range(k)]Calculate next candidates from each prime

next_ugly = min(candidates)Select smallest candidate as next super ugly number

ugly[i] = next_uglyAdd next super ugly number to the list

if candidates[j] == next_ugly: pointers[j] += 1Increment pointers for primes that matched next_ugly

return ugly[-1]Return nth super ugly number

import java.util.*;
public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int k = primes.length;
        int[] ugly = new int[n];
        int[] pointers = new int[k];
        ugly[0] = 1;
        for (int i = 1; i < n; i++) {
            int nextUgly = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                nextUgly = Math.min(nextUgly, primes[j] * ugly[pointers[j]]);
            }
            ugly[i] = nextUgly;
            for (int j = 0; j < k; j++) {
                if (primes[j] * ugly[pointers[j]] == nextUgly) {
                    pointers[j]++;
                }
            }
        }
        return ugly[n - 1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.nthSuperUglyNumber(12, new int[]{2,7,13,19})); // 32
    }
}

Line Notes

int k = primes.length;Number of primes to track

int[] ugly = new int[n];Array to store super ugly numbers

int[] pointers = new int[k];Pointers for each prime's multiple

ugly[0] = 1;Initialize first super ugly number

for (int j = 0; j < k; j++)Calculate candidates for each prime

nextUgly = Math.min(nextUgly, primes[j] * ugly[pointers[j]]);Find minimum candidate

if (primes[j] * ugly[pointers[j]] == nextUgly)Increment pointers for primes that generated nextUgly

return ugly[n - 1];Return nth super ugly number

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int nthSuperUglyNumber(int n, vector<int>& primes) {
    int k = primes.size();
    vector<int> ugly(n, 1);
    vector<int> pointers(k, 0);
    for (int i = 1; i < n; i++) {
        int nextUgly = INT_MAX;
        for (int j = 0; j < k; j++) {
            nextUgly = min(nextUgly, primes[j] * ugly[pointers[j]]);
        }
        ugly[i] = nextUgly;
        for (int j = 0; j < k; j++) {
            if (primes[j] * ugly[pointers[j]] == nextUgly) {
                pointers[j]++;
            }
        }
    }
    return ugly.back();
}

int main() {
    vector<int> primes = {2,7,13,19};
    cout << nthSuperUglyNumber(12, primes) << endl; // 32
    return 0;
}

Line Notes

int k = primes.size();Number of primes

vector<int> ugly(n, 1);Initialize vector for super ugly numbers

vector<int> pointers(k, 0);Pointers for each prime

int nextUgly = INT_MAX;Initialize next ugly number to max

nextUgly = min(nextUgly, primes[j] * ugly[pointers[j]]);Find minimum candidate

ugly[i] = nextUgly;Add next super ugly number

if (primes[j] * ugly[pointers[j]] == nextUgly)Increment pointers for matching primes

return ugly.back();Return nth super ugly number

function nthSuperUglyNumber(n, primes) {
    const k = primes.length;
    const ugly = new Array(n).fill(1);
    const pointers = new Array(k).fill(0);
    for (let i = 1; i < n; i++) {
        let nextUgly = Infinity;
        for (let j = 0; j < k; j++) {
            nextUgly = Math.min(nextUgly, primes[j] * ugly[pointers[j]]);
        }
        ugly[i] = nextUgly;
        for (let j = 0; j < k; j++) {
            if (primes[j] * ugly[pointers[j]] === nextUgly) {
                pointers[j]++;
            }
        }
    }
    return ugly[n - 1];
}

// Test
console.log(nthSuperUglyNumber(12, [2,7,13,19])); // 32

Line Notes

const k = primes.length;Number of primes

const ugly = new Array(n).fill(1);Initialize array for super ugly numbers

const pointers = new Array(k).fill(0);Pointers for each prime

let nextUgly = Infinity;Initialize next ugly number to max

nextUgly = Math.min(nextUgly, primes[j] * ugly[pointers[j]]);Find minimum candidate

ugly[i] = nextUgly;Add next super ugly number

if (primes[j] * ugly[pointers[j]] === nextUgly)Increment pointers for matching primes

return ugly[n - 1];Return nth super ugly number

⏱

Complexity

TimeO(n * k)

SpaceO(n + k)

We generate n super ugly numbers, and for each number, we compute k candidates and update pointers, leading to linear time in n and k.

💡 For n=100000 and k=100, this means about 10 million operations, which is efficient enough for interview constraints.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs and is the standard solution to this problem.

🧠

Optimal Approach (Min-Heap for K-way Merge)

💡 This approach uses a min-heap to efficiently merge k sorted sequences of multiples, providing a clean and scalable solution especially when k is large.

Intuition

Each prime generates a sorted sequence of multiples; use a min-heap to always pick the smallest next candidate and generate new candidates dynamically.

Algorithm

1. Initialize a min-heap and add the first element (1) with index -1 indicating the base.
2. Maintain an array ugly to store super ugly numbers, starting with 1.
3. Pop the smallest element from the heap and add it to ugly if it is not a duplicate.
4. For the popped element, generate the next candidate by multiplying the prime at its index with the next ugly number and push it into the heap.
5. Repeat until the nth super ugly number is found.

💡 This algorithm dynamically generates candidates and uses a heap to efficiently merge sequences, avoiding duplicates by careful checks.

</>

Code

import heapq

def nthSuperUglyNumber(n, primes):
    ugly = [1]
    k = len(primes)
    heap = []
    # Each heap element: (value, prime_index, ugly_index)
    for i, p in enumerate(primes):
        heapq.heappush(heap, (p, i, 0))
    while len(ugly) < n:
        val, i, idx = heapq.heappop(heap)
        if val != ugly[-1]:
            ugly.append(val)
        heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))
    return ugly[-1]

# Driver code
if __name__ == '__main__':
    print(nthSuperUglyNumber(12, [2,7,13,19]))  # Output: 32

Line Notes

import heapqImport heapq for min-heap operations

ugly = [1]Initialize list with first super ugly number

heap = []Initialize min-heap

for i, p in enumerate(primes)Push initial multiples of primes into heap

heapq.heappush(heap, (p, i, 0))Push tuple with value, prime index, and ugly index

val, i, idx = heapq.heappop(heap)Pop smallest candidate from heap

if val != ugly[-1]Avoid duplicates by checking last added number

heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))Push next multiple for this prime

return ugly[-1]Return nth super ugly number

import java.util.*;
public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int k = primes.length;
        int[] ugly = new int[n];
        ugly[0] = 1;
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < k; i++) {
            heap.offer(new int[]{primes[i], i, 0});
        }
        int count = 1;
        while (count < n) {
            int[] curr = heap.poll();
            if (curr[0] != ugly[count - 1]) {
                ugly[count++] = curr[0];
            }
            heap.offer(new int[]{primes[curr[1]] * ugly[curr[2] + 1], curr[1], curr[2] + 1});
        }
        return ugly[n - 1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.nthSuperUglyNumber(12, new int[]{2,7,13,19})); // 32
    }
}

Line Notes

PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));Min-heap ordered by value

heap.offer(new int[]{primes[i], i, 0});Push initial multiples with prime and ugly indices

int[] curr = heap.poll();Pop smallest candidate

if (curr[0] != ugly[count - 1])Avoid duplicates

heap.offer(new int[]{primes[curr[1]] * ugly[curr[2] + 1], curr[1], curr[2] + 1});Push next multiple for prime

return ugly[n - 1];Return nth super ugly number

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int nthSuperUglyNumber(int n, vector<int>& primes) {
    int k = primes.size();
    vector<int> ugly(n);
    ugly[0] = 1;
    auto cmp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b) {
        return get<0>(a) > get<0>(b);
    };
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> heap(cmp);
    for (int i = 0; i < k; i++) {
        heap.emplace(primes[i], i, 0);
    }
    int count = 1;
    while (count < n) {
        auto [val, i, idx] = heap.top(); heap.pop();
        if (val != ugly[count - 1]) {
            ugly[count++] = val;
        }
        heap.emplace(primes[i] * ugly[idx + 1], i, idx + 1);
    }
    return ugly.back();
}

int main() {
    vector<int> primes = {2,7,13,19};
    cout << nthSuperUglyNumber(12, primes) << endl; // 32
    return 0;
}

Line Notes

auto cmp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b)Comparator for min-heap

priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> heap(cmp);Declare min-heap

heap.emplace(primes[i], i, 0);Push initial multiples

auto [val, i, idx] = heap.top(); heap.pop();Pop smallest candidate

if (val != ugly[count - 1])Avoid duplicates

heap.emplace(primes[i] * ugly[idx + 1], i, idx + 1);Push next multiple

return ugly.back();Return nth super ugly number

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }
    bubbleUp(i) {
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (this.heap[parent][0] <= this.heap[i][0]) break;
            this.swap(i, parent);
            i = parent;
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return top;
    }
    bubbleDown(i) {
        const n = this.heap.length;
        while (true) {
            let left = 2 * i + 1, right = 2 * i + 2, smallest = i;
            if (left < n && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
            if (right < n && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
            if (smallest === i) break;
            this.swap(i, smallest);
            i = smallest;
        }
    }
}

function nthSuperUglyNumber(n, primes) {
    const ugly = [1];
    const heap = new MinHeap();
    for (let i = 0; i < primes.length; i++) {
        heap.push([primes[i], i, 0]);
    }
    while (ugly.length < n) {
        const [val, i, idx] = heap.pop();
        if (val !== ugly[ugly.length - 1]) {
            ugly.push(val);
        }
        heap.push([primes[i] * ugly[idx + 1], i, idx + 1]);
    }
    return ugly[ugly.length - 1];
}

// Test
console.log(nthSuperUglyNumber(12, [2,7,13,19])); // 32

Line Notes

class MinHeapCustom min-heap implementation for tuples

heap.push([primes[i], i, 0]);Push initial multiples with prime and index

const [val, i, idx] = heap.pop();Pop smallest candidate

if (val !== ugly[ugly.length - 1])Avoid duplicates

heap.push([primes[i] * ugly[idx + 1], i, idx + 1]);Push next multiple for prime

return ugly[ugly.length - 1];Return nth super ugly number

⏱

Complexity

TimeO(n log k)

SpaceO(n + k)

Each of the n numbers is pushed and popped from a heap of size k, leading to O(n log k) time complexity.

💡 For n=100000 and k=100, this is about 500,000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This heap-based approach is optimal for large k and demonstrates mastery of k-way merging using heaps.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the pointer-based approach is sufficient and efficient; heap approach is good for large k or to demonstrate mastery.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 * k)	O(n^2)	No	N/A	Mention only - never code
2. Pointer-based	O(n * k)	O(n + k)	No	N/A	Code this for most interviews
3. Heap-based	O(n log k)	O(n + k)	No	N/A	Code if k is large or to show heap mastery

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Introduce the pointer-based approach to improve efficiency.Step 4: Discuss the heap-based approach as an optimal solution.Step 5: Code the pointer-based or heap-based approach depending on time.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test & Explain: 8min. Total ~30min

What the Interviewer Tests

The interviewer tests your ability to recognize k-way merging, avoid duplicates, optimize time complexity, and write clean code.

Common Follow-ups

• What if primes array is very large? → Use heap-based approach for better scalability.
• Can you generate super ugly numbers in sorted order without duplicates? → Yes, pointer or heap approach ensures sorted unique output.

💡 These follow-ups test your understanding of scalability and correctness in generating sequences without duplicates.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to generate or merge sequences formed by multiples of given primes or sorted lists, especially when duplicates must be avoided.

Signature Phrases

'super ugly number''prime factors are in the given array''find the nth number in the sequence'

NOT This Pattern When

Problems that require factorization without sequence generation or problems that do not involve merging multiple sorted sequences.

Similar Problems

Ugly Number II - similar prime factorization and sequence generationMerge k Sorted Lists - uses heap to merge multiple sorted sequencesKth Smallest Element in a Sorted Matrix - uses heap for k-way merging

Practice

1. You are given K sorted arrays and need to find the median of all elements combined without fully merging them. Which algorithmic approach guarantees an optimal solution in terms of time complexity for large inputs?

easy

A. Merge all arrays fully into one sorted array and then pick the median.

B. Use binary search on the value range combined with counting elements ≤ mid across arrays.

C. Apply a greedy approach by repeatedly picking the smallest current element from arrays until median is found.

D. Use dynamic programming to build a table of medians for subarrays and combine results.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the median without merging all arrays fully, which is costly for large inputs.

2. Step 2: Identify optimal approach

   Binary search on the value range combined with counting elements ≤ mid leverages sorted arrays and avoids full merge, achieving better time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on value range is known optimal for this problem [OK]

Hint: Binary search on value range beats full merge [OK]

Common Mistakes:

• Assuming full merge is always optimal
• Confusing greedy with binary search
• Misapplying DP to median finding

2. Consider the following Python code implementing the optimal job assignment to K machines. Given K = 2 and jobs = [[0,5],[1,2],[5,3]], what is the final returned list indicating the machine assigned to each job (in original job order)?

easy

A. [0, 1, 0]

B. [0, 0, 1]

C. [1, 0, 1]

D. [1, 1, 0]

Solution

1. Step 1: Sort jobs by start time

   Jobs sorted by start time: (0,[0,5]), (1,[1,2]), (2,[5,3]) with indices 0,1,2 respectively.

2. Step 2: Simulate assignment

   Initially, available machines = [0,1]. - Job 0 starts at 0: assign machine 0, finish at 5. - Job 1 starts at 1: machine 1 is free, assign machine 1, finish at 3. - Job 2 starts at 5: running machines finish times are 3 and 5; both ≤ 5, so both machines become available. Assign machine 0 (smallest index). Result array indexed by original job indices: [0,1,0].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trace matches output [0,1,0] [OK]

Hint: Sort jobs by start time and track machine availability with heaps [OK]

Common Mistakes:

• Assigning machine 1 to job 1 instead of machine 0
• Not freeing machines before assigning next job
• Mixing up job indices after sorting

3. Given the following code snippet for merging k sorted lists using divide and conquer, what is the value of lists[0] after the first iteration of the outer while loop when input lists are:
List 0: 1 -> 4 -> 5
List 1: 1 -> 3 -> 4
List 2: 2 -> 6

easy

A. Merged list starting with 1 -> 1 -> 3 -> 4 -> 4 -> 5

B. Merged list starting with 1 -> 2 -> 3 -> 4 -> 5 -> 6

C. Merged list starting with 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

D. Merged list starting with 1 -> 3 -> 4 -> 5 -> 6

Solution

1. Step 1: Trace first iteration of outer while loop

   Interval = 1, merge lists[0] and lists[1]: merge (1->4->5) and (1->3->4).

2. Step 2: Result of mergeTwoLists(lists[0], lists[1])

   Merged list is 1 -> 1 -> 3 -> 4 -> 4 -> 5. lists[2] remains unchanged.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only first two lists merged in first iteration [OK]

Hint: First merge merges pairs at interval 1 only [OK]

Common Mistakes:

• Merging all lists at once instead of pairs
• Confusing interval doubling
• Assuming full merge after first iteration

4. Consider the following Python code that sorts a k-sorted array using a min-heap. Given arr = [4, 3, 2] and k = 2, what is the value of arr after the function completes?

easy

A. [2, 3, 4]

B. [3, 4, 2]

C. [4, 2, 3]

D. [2, 4, 3]

Solution

1. Step 1: Initialize heap with first k+1 elements

   Heap = [4, 3, 2] -> heapify -> [2, 3, 4]

2. Step 2: Since array length is 3 and k+1=3, no for-loop iterations occur; pop all from heap into arr

   Pop 2 -> arr[0]=2, pop 3 -> arr[1]=3, pop 4 -> arr[2]=4

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap pops in ascending order produce sorted array [2,3,4] [OK]

Hint: Heapify first k+1 elements sorts initial window [OK]

Common Mistakes:

• Forgetting heapify order
• Misindexing target_index
• Assuming for-loop runs when array length ≤ k+1

5. Suppose the problem changes: now you want to find the nth ugly number but you can reuse the same ugly number multiple times in generating new numbers (i.e., duplicates allowed). Which modification to the min-heap approach correctly handles this variant without losing correctness or efficiency?

hard

A. Remove the 'seen' set entirely and push all generated numbers into the heap, allowing duplicates.

B. Keep the 'seen' set but reset it after every iteration to allow reuse of numbers in the next iteration.

C. Use a counter map to track how many times each number is generated and only push if count is below a threshold.

D. Keep the 'seen' set as is to avoid duplicates, since duplicates do not affect correctness or efficiency.

Solution

1. Step 1: Understand the variant allowing duplicates

   Allowing reuse means duplicates are valid and should be generated and processed multiple times.

2. Step 2: Modify the algorithm accordingly

   Removing the 'seen' set allows duplicates to be pushed and popped, correctly reflecting the new problem constraints.

3. Step 3: Consider efficiency

   Though duplicates increase heap size, this is necessary to correctly generate all numbers under the new rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing 'seen' allows duplicates as required [OK]

Hint: Allow duplicates by removing 'seen' when reuse is allowed [OK]

Common Mistakes:

• Keeping 'seen' and missing duplicates
• Resetting 'seen' incorrectly
• Using counters unnecessarily