# Ugly Number II

## Question

Ugly number is a number that only have factors `2`, `3` and `5`.

Design an algorithm to find the nth ugly number. The first `10` ugly numbers are `1, 2, 3, 4, 5, 6, 8, 9, 10, 12...`

Notice

Note that `1` is typically treated as an ugly number.

Example

If `n = 9`, return `10`.

Challenge

O(n log n) or O(n) time.

## Analysis

Dynamic Programming

“The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:

``````(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …``````

We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 …) multiply 2, 3, 5.

Then we use similar merge method as merge sort, to get every ugly number from the three subsequence.

Every step we choose the smallest one, and move one step after,including nums with same value.”

Ref:

https://www.geeksforgeeks.org/ugly-numbers/

PriorityQueue

## Solution

O(n) Scan

``````import java.util.ArrayList;

class Solution {
/**
* @param n an integer
* @return the nth prime number as description.
*/
public int nthUglyNumber(int n) {
if (n == 0 || n == 1) {
return 1;
}
ArrayList<Integer> uglyNumbers = new ArrayList<Integer>();
int p1 = 0;
int p2 = 0;
int p3 = 0;
int current = 2;

for (int i = 0; i < n; i++) {
while (uglyNumbers.get(p1) * 2 < current) {
p1++;
}
int min1 = uglyNumbers.get(p1) * 2;

while (uglyNumbers.get(p2) * 3 < current) {
p2++;
}
int min2 = uglyNumbers.get(p2) * 3;

while (uglyNumbers.get(p3) * 5 < current) {
p3++;
}
int min3 = uglyNumbers.get(p3) * 5;

int next = Math.min(Math.min(min1, min2), min3);
current = next + 1;
}
return uglyNumbers.get(n - 1);
}
}``````

O(n) Scan 2

``````public class Solution {
public int nthUglyNumber(int n) {
int[] ugly = new int[n];
ugly[0] = 1;
int index2 = 0, index3 = 0, index5 = 0;
int factor2 = 2, factor3 = 3, factor5 = 5;
for(int i=1;i<n;i++){
int min = Math.min(Math.min(factor2,factor3),factor5);
ugly[i] = min;
if(factor2 == min)
factor2 = 2*ugly[++index2];
if(factor3 == min)
factor3 = 3*ugly[++index3];
if(factor5 == min)
factor5 = 5*ugly[++index5];
}
return ugly[n-1];
}
}``````

O(n) A more concise version

``````    public int nthUglyNumber(int n) {
int[] nums = new int[n];
int index2 = 0, index3 = 0, index5 = 0;
nums[0] = 1;
for(int i = 1; i < nums.length; i++){
nums[i] = Math.min(nums[index2] * 2, Math.min(nums[index3] * 3, nums[index5] * 5));
if(nums[i] == nums[index2] * 2)
index2++;
if(nums[i] == nums[index3] * 3)
index3++;
if(nums[i] == nums[index5] * 5)
index5++;
}
return nums[n - 1];
}``````

O(nlogn) HashMap + Heap (use HashMap to dedupe element in Heap)

``````class Solution {
/**
* @param n an integer
* @return the nth prime number as description.
*/
public int nthUglyNumber(int n) {
Queue<Long> Q = new PriorityQueue<Long>();
HashSet<Long> inQ = new HashSet<Long>();
Long[] primes = new Long[3];
primes[0] = Long.valueOf(2);
primes[1] = Long.valueOf(3);
primes[2] = Long.valueOf(5);
for (int i = 0; i < 3; i++) {
}
Long number = Long.valueOf(1);
for (int i = 1; i < n; i++) {
number = Q.poll();
for (int j = 0; j < 3; j++) {
if (!inQ.contains(primes[j] * number)) {
}
}
}
return number.intValue();
}
}``````

Heap - PriorityQueue

``````class Solution {
public int nthUglyNumber(int n) {
if(n <= 0){
return 0;
}

PriorityQueue<Long> pq = new PriorityQueue<>();

pq.offer(1l);

for(int i = 0; i < n-1; i++){
long tmp = pq.poll();

while(!pq.isEmpty() && pq.peek() == tmp){
tmp = pq.poll();
}

pq.offer(tmp * 2);
pq.offer(tmp * 3);
pq.offer(tmp * 5);
}

return pq.poll().intValue();
}
}``````

DP + DFS (2ms AC)

``````class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
return DFS(dp, 1, 0, 0, 0, n);
}

private int DFS(int[] dp, int i, int p2, int p3, int p5, int n) {
if (i == n) return dp[n - 1];
dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
if (dp[i] == dp[p2] * 2) p2++;
if (dp[i] == dp[p3] * 3) p3++;
if (dp[i] == dp[p5] * 5) p5++;
return DFS(dp, i + 1, p2, p3, p5, n);
}
}``````

Last updated