Ugly Number II - Dynamic Programming

LeetCode July Challange [Week 1]

Write a program to find the nth ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

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.

Note:

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

Solutions:

Brute Force

Loop for all positive integers until ugly number count is smaller than n if an integer is ugly than increment ugly number count.

To validate if a number is ugly, divide the number by greatest divisible powers of 2, 3, and 5 if the number becomes 1 then it is an ugly number otherwise not.

This method is not time efficient as it checks for all integers until ugly number count becomes n, but the space complexity of this method is O(1)

Method 2 (Use Dynamic Programming)
Here is a time-efficient solution with O(n) extra space. The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence into three groups as below:

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. It’s a 3-way merge. Every step we choose the smallest one and move one step after. Move the corresponding pointer by one step. Repeat till you’ll have n ugly numbers.

Happy Coding!!!