nth Ugly Number

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

First Attempt

We can see that an ugly number is a multiple of either 2, 3 or 5. Only exception is that 1 is also ugly. Starting from 1 can we multiply 1 by 2, 3, and 5 then can we get next 3 ugly numbers {2, 3, 5}? No, because there is one more ugly number 4 before 5. So it is obvious that each time we pick min ugly and compute all the numbers multiples of 2,3, and 5 of that number and add it to a data structure. Next time we pick the minimum and so on. Which data structures fit where we aways get min in O(1) time? Answer is MinHeap.

So, we will keep a min heap and initially push 1 as the first ugly number. The heap is {1}. Now, for next ugly number we extract min 1 from heap and push the multiples of 2, 3, and 5. Now, the heap becomes {2, 3, 5}. For next ugly we extract min from heap which is 2. SO, we push 2*2=4, 2*3=6, 2*5=10 into the heap and the heap becomes {3, 4, 5, 6, 10}. Next we extract 3 and push 3*2=6, 3*3=9, and 3*5=15. Note that, we already pushed 6 so we should not push another 6 into heap. Now heap becomes {4, 5, 6, 9, 10, 15}. And so on.

What is the complexity of the above algorithm? We extract one element at each step until we extract n element to get the nth ugly. Each extract triggers a heapify operation to maintain heap property which take O(lgn) on average. So, total complexity os O(ngln).

Below is a simple implementation of the above idea using PriorityQueue as min heap and as HashSet to track elements already pushed and avoid pushing duplicates. The worst time complexity is O(nlgn). Note that , we need to handle overflow cases when multiplication of a ugly number with 2, 3, or 5 may overflow the integer. We just ignore these values as they are too big to reach at the top of the min heap.

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;
}

Faster Solution
Note that, in the previous idea we are technically computing many duplicate ugly numbers. For example, 10 can be generated as 5*2 or 2*5. So, we could potentially improve by caching the computation is DP table. How?

Note that, each ugly number is being taken from one of the three sequences generated by multiple of 2, 3 or 5 respectively. We always take the min from these 3 sequences. For example, the 3 sequences looks like –

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

we take the elements in order of -
1*2, 1*3, 2*2, 1*5, 2*3, 3*3, 2*5, ...

If we look closely then we will see that this is a simple merge procedure we do in Merge Sort. Here instead of two sorted array we have 3 sorted array and we keep 3 pointers to do a 3-way merge. Each time we take the minimum value pointed by 3 pointers and then increment the pointers. Note, that in order to avoid taking duplicates we need to increment pointer that points to same value across 3 sequences. So, unlike merge sort we may increment more than one pointers while taking a value.

For example,

p2
|
v
1*2, 2*2, 3*2, 4*2, ...

p3
|
v
1*3, 2*3, 3*3, 4*3, ...

p5
|
v
1*5, 2*5, 3*5, 4*5, ...


we take 1*2. increment p2.


    p2
     |
     v
1*2, 2*2, 3*2, 4*2, ...

p3
|
v
1*3, 2*3, 3*3, 4*3, ...

p5
|
v
1*5, 2*5, 3*5, 4*5, ...


Similarly, we take 1*3 increment p3, then we take 2*2 and increment p2, then we take 1*5 and increment p5

          p2
          |
          v
1*2, 2*2, 3*2, 4*2, ...

    p3
     |
     v
1*3, 2*3, 3*3, 4*3, ...

    p5
     |
     v
1*5, 2*5, 3*5, 4*5, ...


Now, we take either 2*3 or 3*2 (as both have same value 6) and increment both p2 and p3 as they point to same value. And so on.

What is the complexity? This is certainly a O(n) time solution. We use a dp table to store the merged sequence. Below is a simple implementation of this idea.

public static int nthUglyDP(int n){
	int merged[] = new int[n];
	//1 is considered as ugly so, its the first ugly number
	merged[0] = 1;
	//pointer to the three sets of ugly numbers generated by multiplying respectively by 2, 3, and 5
	//p2 points to current ugly of the sequence : 1*2, 2*2, 3*2, 4*2, ...
	//p3 points to current ugly of the sequence : 1*3, 2*3, 3*3, 4*3, ...
	//p5 points to current ugly of the sequence : 1*5, 2*5, 3*5, 4*5, ...
	int p2 = 0, p3 = 0, p5 = 0;
	
	//merge the 3 sequences pointed by p2, p3, and p5 and always take the min as we do in merge sort
	for(int i = 1; i<n; i++){
		merged[i] = Math.min(Math.min(merged[p2]*2, merged[p3]*3), merged[p5]*5);
		
		//now increment the corrsponding pointer - same number can be generated in multiple sequences
		//for example, 10 can be genetaed by 2 as 5*2 or by 5 as 2*5. So, we increment all pointers 
		//that contains same value to avoid duplicates
		if(merged[i] == merged[p2]*2){
			p2++;
		}
		if(merged[i] == merged[p3]*3){
			p3++;
		}
		if(merged[i] == merged[p5]*5){
			p5++;
		}
	}
	
	return merged[n-1];
}