Problem

Given an integer n, return the nth ugly number.

Ugly Number Definition

Examples

Example 1:

1
2
3

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

1
2
3

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Similar Problems

Solution

Method 1 - Brute Force

Iterate through all positive integers until the count of ugly numbers reaches n; increment the count if the integer is ugly.

To determine if a number is ugly, divide it by the highest powers of 2, 3, and 5 that it is divisible by. If the result is 1, the number is ugly; otherwise, it is not.

For example, to check if 300 is ugly: divide 300 by 4 (highest power of 2) to get 75, then divide 75 by 3 (highest power of 3) to get 25, and finally, divide 25 by 25 (highest power of 5) to get 1. Since the result is 1, 300 is an ugly number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {

	public int nthUglyNumber(int n) {
		int i = 1;
		int count = 1; /* ugly number count */

		while (n > count) {
			i++;

			if (isUgly(i)) {
				count++;
			}
		}

		return i;
	}

	private int isUgly(int no) {
		no = maxDivide(no, 2);
		no = maxDivide(no, 3);
		no = maxDivide(no, 5);

		return (no == 1) ? 1 : 0;
	}

	private int maxDivide(int a, int b) {
		while (a % b == 0) {
			a = a / b;
		}

		return a;
	}
}

Complexity

  • ⏰ Time complexity: O(n * log2(n)) - IsUgly takes log2(n) time, and we have to find n numbers. Actually it is i log2(n), but finding i is hard.
  • 🧺 Space complexity: O(1)

Method 2 - Using Dynamic Programming

  1. Create an array for ugly numbers, initializing the first element with 1, i.e., ugly[0] = 1.

  2. Set up three index variables, i, j, and k, to all point to the first element: i = j = k = 0;

  3. Prepare the next multiples of 2, 3, and 5:

    1
2
3

     m2 = ugly[i] * 2; 
 m3 = ugly[j] * 3; 
 m5 = ugly[k] * 5;

  4. Loop until the array contains n ugly numbers:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

     min = min(m2, m3, m5);
 ugly[u] = min;
if (min == m2) {
   i++;
}
if (min == m3) {
   j++;
}
if (next_ugly_no == m5) {
    k++;
}

  5. Return the last computed ugly number. The order in which we process the elements would look like:

1

1*2, 1*3, 2*2, 1*5, 2*3, 3*3, 2*5, ...

This process is similar to a 3-way merge procedure found in Merge Sort, as we manage three lists sorted by multiplying 2, 3, and 5, and use three pointers to merge these lists. By selecting the smallest value and updating the corresponding pointer, we ensure each minimum value is utilized and avoid duplicates by potentially incrementing more than one pointer at a time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {

	public int nthUglyNumber(int n) {
		if (n <= 0)
			return 0;

		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(1);

		int i = 0;
		int j = 0;
		int k = 0;

		while (list.size()<n) {
			int m2 = list.get(i) * 2;
			int m3 = list.get(j) * 3;
			int m5 = list.get(k) * 5;

			int min = Math.min(m2, Math.min(m3, m5));
			list.add(min);

			if (min == m2) {
				i++;
			}

			if (min == m3) {
				j++;
			}

			if (min == m5) {
				k++;
			}
		}

		return list.get(list.size() - 1);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {

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

		int[] ans = new int[n];
		ans[0] = 1;
		int u = 1; //index for ans
		int i = 0;
		int j = 0;
		int k = 0;

		while (u < n) {
			int m2 = ans[i] * 2;
			int m3 = ans[j] * 3;
			int m5 = ans[k] * 5;

			int min = Math.min(m2, Math.min(m3, m5));
			ans[u++] = min;

			if (min == m2) {
				i++;
			}

			if (min == m3) {
				j++;
			}

			if (min == m5) {
				k++;
			}
		}

		return ans[n - 1];
	}
}
1

> I prefer above function for simplicity, but we can avoid recalculating m2, m3 and m5.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Dry Run

1
2
3
4
5

n = 7
int[] ans = new int[7];
ans[0] = 1; // First ugly number
int u = 1;
int i = 0, j = 0, k = 0;
Loop Iterations
Iteration 1
1
2
3
4
5
6
7

int m2 = ans[0] * 2 = 2;
int m3 = ans[0] * 3 = 3;
int m5 = ans[0] * 5 = 5;
int min = Math.min(2, Math.min(3, 5)) = 2;
ans[1] = 2; // ans = [1, 2, ...]
u++; // u = 2
if (min == 2) i++; // i = 1
Iteration 2
1
2
3
4
5
6
7

int m2 = ans[1] * 2 = 4;
int m3 = ans[0] * 3 = 3;
int m5 = ans[0] * 5 = 5;
int min = Math.min(4, Math.min(3, 5)) = 3;
ans[2] = 3; // ans = [1, 2, 3, ...]
u++; // u = 3
if (min == 3) j++; // j = 1
Iteration 3
1
2
3
4
5
6
7

int m2 = ans[1] * 2 = 4;
int m3 = ans[1] * 3 = 6;
int m5 = ans[0] * 5 = 5;
int min = Math.min(4, Math.min(6, 5)) = 4;
ans[3] = 4; // ans = [1, 2, 3, 4, ...]
u++; // u = 4
if (min == 4) i++; // i = 2
Iteration 4
1
2
3
4
5
6
7

int m2 = ans[2] * 2 = 6;
int m3 = ans[1] * 3 = 6;
int m5 = ans[0] * 5 = 5;
int min = Math.min(6, Math.min(6, 5)) = 5;
ans[4] = 5; // ans = [1, 2, 3, 4, 5, ...]
u++; // u = 5
if (min == 5) k++; // k = 1
Iteration 5
1
2
3
4
5
6
7
8

int m2 = ans[2] * 2 = 6;
int m3 = ans[1] * 3 = 6;
int m5 = ans[1] * 5 = 10;
int min = Math.min(6, Math.min(6, 10)) = 6;
ans[5] = 6; // ans = [1, 2, 3, 4, 5, 6, ...]
u++; // u = 6
if (min == 6) i++; // i = 3
if (min == 6) j++; // j = 2
Iteration 6
1
2
3
4
5
6
7

int m2 = ans[3] * 2 = 8;
int m3 = ans[2] * 3 = 9;
int m5 = ans[1] * 5 = 10;
int min = Math.min(8, Math.min(9, 10)) = 8;
ans[6] = 8; // ans = [1, 2, 3, 4, 5, 6, 8, ...]
u++; // u = 7
if (min == 8) i++; // i = 4
Final Result

We return ans[6] = 11 is answer.

Method 3 - Using Minheap and Set

As we are again and again getting minimum number, may be minHeap is a good idea.

Below is a straightforward implementation of the idea using a PriorityQueue as a min-heap and a HashSet to track inserted elements and avoid duplicates. The worst-case time complexity is (O(n log n)). It’s important to handle overflow cases when multiplying an ugly number by 2, 3, or 5, as these values can exceed the integer limit. These overflowing values are ignored since they are too large to reach the top of the min-heap.

Of course this is not the fastest solution, but it is also not bad. DP is the best.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public static int nthUglyNumber(int n) {
	int nthUgly = 1;
	PriorityQueue<Integer> minHeap = new PriorityQueue<Integer> ();
	Set<Integer> uniques = new HashSet<Integer> ();
	minHeap.offer(1);

	while (n > 0) {
		nthUgly = minHeap.poll();
		int next = nthUgly * 2;
		if (nthUgly<= Integer.MAX_VALUE / 2 && !uniques.contains(next)) {
			minHeap.offer(next);
			uniques.add(next);
		}
		next = nthUgly * 3;
		if (nthUgly<= Integer.MAX_VALUE / 3 && !uniques.contains(next)) {
			minHeap.offer(next);
			uniques.add(next);
		}
		next = nthUgly * 5;
		if (nthUgly<= Integer.MAX_VALUE / 5 && !uniques.contains(next)) {
			minHeap.offer(next);
			uniques.add(next);
		}
		n--;
	}

	return nthUgly;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method 4 - Using MinHeap and No Set

Actually min heap’s peek will always have minimum element. So, when we poll out the element, we can check peek of heap is still the same, and just poll them out. So, no need to use set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int nthUglyNumber(int n) {
	if(n==1) return 1;
	PriorityQueue<Long> q = new PriorityQueue();
	q.add(1l);

	for(long i=1; i<n; i++) {
		long tmp = q.poll();
		while(!q.isEmpty() && q.peek()==tmp) tmp = q.poll();

		q.add(tmp*2);
		q.add(tmp*3);
		q.add(tmp*5);
	}
	return q.poll().intValue();
}

Method 5 - Using TreeSet

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {

	public int nthUglyNumber(int n) {
		TreeSet<Long> treeset = new TreeSet();
		treeset.add(1L);
		int c = 1;

		while (c < n) {
			long x = treeset.pollFirst();
			c++;
			treeset.add(x * 2);
			treeset.add(x * 3);
			treeset.add(x * 5);
		}

		return (int)((long) treeset.pollFirst());
	}
}

Complexity

  • ⏰ Time complexity: O(n log(n)) - In worst case treeset will have n elements, and adding and removing new elements take log(n) time. So, overall O(n log(n)).
  • 🧺 Space complexity: O(1)