Ugly Numbers is a famous problem asked in many coding interviews and coding rounds. In this article we will be explaining dynamic programming solution with C++ code of this problem.
Ugly Numbers Problem Description
An ugly number is a number whose prime factors are only 2, 3 & 5. In other words, a number X must be of form X = 2^a * 3^b * 5^c. Given an integer n, return nth ugly number.
- Single line input containing an integer n.
- The required number.
- The First 5 ugly numbers are : 1, 2, 3, 4 & 5.
Ugly Numbers Problem Solution
- We know the first ugly number is 1.
- We create a dp array to where dp[n-1] = nth ugly number (0 based indexing). This means dp = 1;
- Now we know nth ugly number will be minimum of all previous numbers multiplied by 2,3 or 5 & the number should be greater than previous ugly number. If we find this iteratively, this would make our solution O(n^2).
- To further reduce the time complexity to O(n) we keep track of minimum next multiples of 2, 3 & 5 and corresponding minimum indicies of dp array. We then use these to find next number. Refer to code below for more details.
Time Complexity – O(n)
Space Complexity – O(n)
Nth ugly number is 12