Find Nth Ugly Number
Ugly numbers are those whose factors are multiples of 2,3 and 5 only. 1 is included by convention.
So the first few ugly numbers are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
Naive approach to this is testing every number for ugliness.
If it's ugly, increment uglyFoundCount and consider higher numbers till uglyFoundCount reaches N
Dynamic Programming can be applied to this if we can formulate Ugly(n) in terms of Ugly(k) where k < n
If we have k ugly numbers already, then the k+1 ugly number has to be
some multiple of the previous ugly numbers only else it would not remain ugly.
We need to multiply previous ugly numbers by 2,3 and 5 and choose the next highest.
But if we multiply all the previous numbers by 2,3 and 5 then it will become thrice O(n2)
operations to find all such multiples and then another O(n) operations to find the minimum among them.
To optimize, we will keep track where last multiple of each (2,3,5) was
kept.
If we know that, then we need not consider ugly numbers previous to those.
With these considerations, the following DP solution can be written:
| Code | Sample Execution |
|
| i | i2 | i3 | i5 | next_m2 | next_m3 | next_m5 | arr[i] |
| 0 | 0 | 0 | 0 | 2 | 3 | 5 | 1 |
| 1 | 1 | 0 | 0 | 4 | 3 | 5 | 2 |
| 2 | 1 | 1 | 0 | 4 | 6 | 5 | 3 |
| 3 | 2 | 1 | 0 | 6 | 6 | 5 | 4 |
| 4 | 2 | 1 | 1 | 6 | 6 | 10 | 5 |
| 5 | 3 | 1 | 1 | 8 | 6 | 10 | 6 |
| 6 | 3 | 2 | 1 | 8 | 9 | 10 | 6 |
| 6 | 4 | 2 | 1 | 10 | 9 | 10 | 8 |
| 7 | 4 | 3 | 1 | 10 | 12 | 10 | 9 |
| 8 | 5 | 3 | 1 | 12 | 12 | 10 | 10 |
| 9 | 5 | 3 | 2 | 12 | 12 | 15 | 10 |
| 9 | 6 | 3 | 2 | 16 | 12 | 15 | 12 |
|
The sample execution shows a bug in the above logic.
It is possible that some numbers could get repeated in the final output, so its necessary to check
the number's existence before putting it in the array.
This can be done by modifying line 19 in the above code to the following:
if (!ugly.contains(next_ugly_no))
ugly[i] = next_ugly_no;
But this will make the entire program O(n2)
A better bet for checking the contains function is to implement it yourself.
Two things can be done if its a custom implementation:
- Binary search: Because this is a sorted array, binary search can be used to get an overall order of O(n log n)
- Search from end: The number to be searched will be very close to the end of the arr, so it makes sense to search it from the end.
In theory, this will be still be O(n2), but in practice, it will be closer to O(n)
Or better still, duplicates can be removed from the output array in O(n) (since its sorted).
So to get Nth ugly number, find 2N ugly numbers and remove duplicates.
All in O(n)
|
