Ugly numbers
Ugly is a number whose only prime factors include 2, 3, and 5. 1 is considered to be ugly by convention.
For example, 4 (2×2), 6 (2×3), 20 (2 *2 * 5) are ugly numbers but 7 (1x 7), 28(2x14x7) are not.
A simple way to calculate if a number is ugly or not would be to keep dividing a given number by 2, 3, and 5 and if we get 1 at the end, the number is ugly. Consider 300 for example.
300 – keep dividing by 2 till it can possibly be divisible -> 150, 75
75 – keep diving by 3 till it can possibly be divisible -> 25
25 – keep dividing by 5 till it can possibly be divisible -> 5 -> 1
Since we got 1 at the end, 300 is an ugly number.
So, what’s the time complexity of such an algorithm? It would O(nxn) with O(1) space complexity.
Can we do better? Whenever optimization comes to my head, I think of one of the two things – dynamic programming or graphs. Let’s take another look at this problem.
1. What’s the first ugly number? It’s 1. Alright, good enough.
2. What’s next? It would be one of the three – 1×2, 1×3, 1×5 i.e. (2, 3, 5). What’s the smallest? It’s 2. Thus, 2 is our next ugly number.
3. What’s next? It would be one of the three – 2×2, 1×3, 1×5 i.e. (4, 3, 5). What’s the smallest? It’s 3. Thus, 3 is our next ugly number. Note that we didn’t multiple 2 by 1 but instead we multiplied 2 by 2. This is because we had already used 2 in step 2. Now that we have used 3 in this step, we would do the same if we have to use 3 again in the future.
4. What’s next? Minimum of (2×2, 3×3, 1×5) = 4. Thus, 4 is our next ugly number.
5. We keep repeating the procedure till we get what nth ugly number we are looking for.
HERE is some code that solves it using both brute force and dynamic programming.
If you want to see the time difference between the two, figure 1 shows the time to calculate 1500th ugly number using brute force (more than 36 seconds) vs. dynamic programming (less than 2 seconds).
More on dynamic programming later. If you have any questions, let me know in the comments section.
References:
1. GeeksforGeeks 2017. “Ugly Numbers”. https://www.geeksforgeeks.org/ugly-numbers/. [Online; accessed 12-Feb-2018].
2. jmty0083, LeetCode 2017. “Ugly Number II”. https://leetcode.com/problems/ugly-number-ii/discuss/69364/My-16ms-C++-DP-solution-with-short-explanation. [Online; accessed 12-Feb-2018].