Make delicious recipes!

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:

CodeSample 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:
  1. Binary search: Because this is a sorted array, binary search can be used to get an overall order of O(n log n)
  2. 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)






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal