Super Ugly Number - Practice Coding Problems

Super Ugly Number - Problem

A super ugly number is a positive integer whose prime factors are all contained in the given array primes.

Given an integer n and an array of integers primes, return the n^th super ugly number.

The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Input & Output

Example 1 — Basic Case

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

› Output: 32

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

Example 2 — Small Input

$ Input: n = 1, primes = [2,3,5]

› Output: 1

💡 Note: 1 is the first super ugly number for any prime array.

Example 3 — Single Prime

$ Input: n = 5, primes = [3]

› Output: 81

💡 Note: With only prime 3, the sequence is [1,3,9,27,81]. The 5th number is 81 = 3⁴.

Constraints

1 ≤ n ≤ 10⁶
1 ≤ primes.length ≤ 100
2 ≤ primes[i] ≤ 1000
primes[i] is a prime number
All the values of primes are unique and sorted

Visualization

Tap to expand

Understanding the Visualization

Input

n=12, primes=[2,7,13,19] → find 12th super ugly number

Generate

Build sequence: 1,2,4,7,8,13,14,16,19,26,28,32...

Output

12th number is 32

Key Takeaway

🎯 Key Insight: Each super ugly number is formed by multiplying an existing super ugly number with one of the given primes

Asked in

G Google 45 f Facebook 32 a Amazon 28 M Microsoft 22

The key insight is that super ugly numbers can be generated by multiplying existing super ugly numbers with given primes. The optimal approach uses dynamic programming with multiple pointers, maintaining a pointer for each prime to track which existing number to multiply next. This generates numbers in sorted order efficiently. Time: O(n×k), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Priority Queue (Heap) Approach	O(n × k × log(n × k))	O(n × k)	Use min-heap to always get the next smallest super ugly number
Dynamic Programming with Pointers	O(n × k)	O(n)	Generate super ugly numbers in order using multiple pointers
Brute Force Check	O(n × k × log(max_number))	O(1)	Check each number sequentially to see if it's a super ugly number

Priority Queue (Heap) Approach — Algorithm Steps

Initialize min-heap with 1
Pop minimum from heap as next super ugly number
Push all multiples of this number with given primes
Use set to avoid duplicate numbers in heap

Visualization

Tap to expand

Step-by-Step Walkthrough

Pop Minimum

Remove smallest number from heap

Generate Multiples

Create new candidates by multiplying with primes

Push New Numbers

Add non-duplicate candidates to heap

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_HEAP_SIZE 100000

typedef struct {
    long long data[MAX_HEAP_SIZE];
    int size;
} MinHeap;

void heapPush(MinHeap* heap, long long val) {
    int idx = heap->size++;
    heap->data[idx] = val;
    
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap->data[parent] <= heap->data[idx]) break;
        
        long long temp = heap->data[parent];
        heap->data[parent] = heap->data[idx];
        heap->data[idx] = temp;
        idx = parent;
    }
}

long long heapPop(MinHeap* heap) {
    long long min = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    
    int idx = 0;
    while (1) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        int smallest = idx;
        
        if (left < heap->size && heap->data[left] < heap->data[smallest])
            smallest = left;
        if (right < heap->size && heap->data[right] < heap->data[smallest])
            smallest = right;
            
        if (smallest == idx) break;
        
        long long temp = heap->data[idx];
        heap->data[idx] = heap->data[smallest];
        heap->data[smallest] = temp;
        idx = smallest;
    }
    
    return min;
}

int solution(int n, int* primes, int primesSize) {
    MinHeap heap = {.size = 0};
    heapPush(&heap, 1);
    
    // Simple seen array for small values
    int seen[MAX_HEAP_SIZE] = {0};
    seen[1] = 1;
    
    long long ugly = 1;
    for (int i = 0; i < n; i++) {
        ugly = heapPop(&heap);
        
        for (int j = 0; j < primesSize; j++) {
            long long newUgly = ugly * primes[j];
            if (newUgly < MAX_HEAP_SIZE && !seen[newUgly]) {
                seen[newUgly] = 1;
                heapPush(&heap, newUgly);
            }
        }
    }
    
    return (int) ugly;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %s", line);
    
    int primes[100];
    int primesSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        primes[primesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(n, primes, primesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k × log(n × k))

For each of n numbers, we do k heap insertions, each taking O(log(heap_size))

⚡ Linearithmic

Space Complexity

O(n × k)

Heap can grow to O(n×k) size, plus set for deduplication

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~25 min Avg. Time

1.6K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Priority Queue (Heap) Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler