Ugly Numbers

Refer to the Example and Explanation sections for more details and the Approach section to understand how to find the n-th ugly number.

As we know that the sequence of the ugly number is: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … Apart from this, we also know that every number of the series can be divided by 2, 3, and 5 only. So, the above sequence can be rewritten in the form:

• 1×2, 2×2, 3×2, 4×2, 5×2, …
• 1×3, 2×3, 3×3, 4×3, 5×3, …
• 1×5, 2×5, 3×5, 4×5, 5×5, …

So, we can conclude that the above sequence of the ugly numbers can be written in the form of an ugly number sequence multiplied by 2, 3, and 5. In this way, we can generate the arrays of the smaller ugly numbers sequence and then simply merge these sequences.

Refer to the next sub-section for the algorithm.

Algorithm

• Create a function namely findUglyNumbers() that takes an input number n.

1. Declare a dp array that will store the n ugly numbers.
2. As we know that the first ugly number is 1 so initialize the first ugly number in the dp array as: dp[0] = 1.
3. Now, initialize three variables to point to the first element of the array numbers (dp array) as:
   • i2 = i3 = i5 = 0 (Since, 2,3, and 5 are the prime factors of ugly numbers so we have decided the names according to that).
4. Initialize the next three choices of the ugly numbers as they can easily be obtained by multiplying the number dp[0] with 2, 3, and 5.
   • nextMultipleOf2 = dp[i2] * 2;
   • nextMultipleOf3 = dp[i3] * 3;
   • nextMultipleOf5 = dp[i5] * 5;
5. Now, we will run a loop and find the n possible ugly numbers. Inside the loop we will perform certain steps:
   • We will find the next ugly number as the next ugly number would be simply the minimum of the next multiples of 2, 3, and 5.
   • We will now insert the next ugly number at the i-th position in the dp array as it is the i-th ugly number.
   • Now, we will perform simple checks to update the next multiples.
6. Finally, we will return the nextUglyNumber as result.

Refer to the next sub-section for the code implementation in various programming languages.

Code Implementation

Let us see the code for the above-discussed algorithm.

C++ Code

Java Code

Python Code

Output

Time Complexity

The time complexity for finding the nth ugly number using the dynamic programming approach comes out to be O(n), where n is the provided input number.

Space Complexity

Since we are using an extra space of dp array, the space complexity for finding the nth ugly number using the dynamic programming approach comes out to be O(n).

In this approach, we will first generate the three ugly numbers and then store the minimum of the three generated ugly numbers that resemble the ith ugly number. This ith ugly number will be stored at the first position in the set data structure.

Refer to the next sub-section for the algorithm.

Algorithm

• Create a function namely findUglyNumbers() that takes an input number n.

1. Define the base case that the number lies between 1 to 5 then return the number itself as the nth ugly number.
2. Insert the number $1$ as the first ugly number in the set.
3. Find the beginning element of the set and add the next multiples of 2, 3, and 5 (multiplied with the first element of the set) into the set.
   • Example: if the set's first element = x, then insert the following number into the set:
     • x * 2
     • x * 3
     • x * 5
4. Sort the set and decrement and repeat the above steps by decreasing the value of n.
5. At last, return the first element of the set as the nth ugly number.

Refer to the next sub-section for the code implementation in various programming languages.

Code Implementation

Let us see the code for the above-discussed algorithm.

C++ Code

Java Code

Python Code

Output

In this approach to finding the nth ugly number, we are using a set data structure to store the result and we are traversing the numbers from 1 to n.

Time Complexity

The time complexity for finding the nth ugly number using the set data structure approach comes out to be roughly O(n log n).

Space Complexity

Since we are using an extra space of set data structure, the space complexity for finding the n-th ugly number using the set data structure approach comes out to be O(n), where n is the size of the set.

We can use the range of ugly numbers i.e. from $1$ to $21474836647$. We can repeatedly divide this range to get our desired result.

Refer to the next sub-section for the algorithm.

Algorithm

• Create a function namely findUglyNumbers() that takes an input number n.

1. Define the lower and upper bound of the number i.e. 1 to 21474836647.
2. Start searching in the specified range.
3. Find the mid value of the range, and then check for the mid value. If the mid value is larger then shift the higher range to mid (low is the same and high becomes mid) else shift the lower range to mid+1 (high is the same and low becomes mid+1).

Refer to the next sub-section for the code implementation in various programming languages.

Code Implementation

Let us see the code for the above-discussed algorithm.

C++ Code

Java Code

Python Code

Output

We are using an iterative binary search and dividing the range of the ugly numbers into halves in each iteration. We are not using any extra space for performing the binary search.

Time Complexity

The time complexity for finding the nth ugly number using the binary search approach comes out to be O(log n).

Space Complexity

Since we are not using any extra space apart from some variables, the space complexity for finding the nth ugly number using the binary search approach comes out to be O(1).