Table of Contents

# Super Ugly Number – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

A **super ugly number** is a positive integer whose prime factors are in the 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.

**Example 1:**

Input:n = 12, primes = [2,7,13,19]Output:32Explanation:[1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

**Example 2:**

Input:n = 1, primes = [2,3,5]Output:1Explanation:1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

**Constraints:**

`1 <= n <= 10`

^{5}`1 <= primes.length <= 100`

`2 <= primes[i] <= 1000`

`primes[i]`

is**guaranteed**to be a prime number.- All the values of
`primes`

are**unique**and sorted in**ascending order**.

# C++ Super Ugly Number LeetCode Solution

```
``````
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> index(primes.size(), 0), ugly(n, INT_MAX);
ugly[0]=1;
for(int i=1; i<n; i++){
for(int j=0; j<primes.size(); j++) ugly[i]=min(ugly[i],ugly[index[j]]*primes[j]);
for(int j=0; j<primes.size(); j++) index[j]+=(ugly[i]==ugly[index[j]]*primes[j]);
}
return ugly[n-1];
}
```

# Java Super Ugly Number LeetCode Solution

```
``````
public int nthSuperUglyNumberI(int n, int[] primes) {
int[] ugly = new int[n];
int[] idx = new int[primes.length];
ugly[0] = 1;
for (int i = 1; i < n; i++) {
//find next
ugly[i] = Integer.MAX_VALUE;
for (int j = 0; j < primes.length; j++)
ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);
//slip duplicate
for (int j = 0; j < primes.length; j++) {
while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
}
}
return ugly[n - 1];
}
```

# Python 3 Super Ugly Number LeetCode Solution

```
``````
def nthSuperUglyNumber(self, n, primes):
uglies = [1]
def gen(prime):
for ugly in uglies:
yield ugly * prime
merged = heapq.merge(*map(gen, primes))
while len(uglies) < n:
ugly = next(merged)
if ugly != uglies[-1]:
uglies.append(ugly)
return uglies[-1]
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below