Last Updated: 17 Nov, 2021
Ugly Numbers
Moderate
Asked in companies
Ugly numbers are those numbers whose only prime factors are 2, 3, and 5. The first seven ugly numbers are 1, 2, 3, 4, 5, 6, 8, where 1 is an exception. You are given an integer ‘N’, print the ‘Nth’ ugly number. As the ugly number can be large, print the result modulo 10^9 + 7.
For example:
Let ‘N’ be: 10
The 10th ugly number is: 12
Input Format :
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case contains a single integer ‘N’.
Output Format :
For each test case, print a single integer representing the ‘Nth’ ugly number.
Print the output of each test case in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
Time Limit: 1 sec
Approaches
The basic idea is to find the count of ugly numbers present less than a given number ‘N’. We use binary search to find the count. We initialize a range in which the result will be present and then use binary search to find the count of ugly numbers smaller than a number. We find it by finding the count of ugly numbers which are multiples of 2, 3, and 5, multiples of both 2 and 3, 3 and 5, and 2 and 5, and multiple of 2, 3, and 5.
Here is the algorithm :
- Create a variable (say, ‘ANS’) used to store the result.
- Initialize a range (say, ‘LOW’ and ‘HIGH’) where the result will lie.
- Run a loop till ‘LOW’ is smaller than equal to ‘HIGH’.
- Create a variable (say, ‘MID’) and initialize it with an average of ‘LOW’ and ‘HIGH’.
- Check if the count of ugly numbers till ‘MID’ is greater than equal to ‘N’ by calling the HELPER function.
- Update ‘ANS’ by ‘MID’.
- Update ‘HIGH’ by ‘MID’ - 1.
- Else
- Update ‘LOW’ by ‘MID’ + 1.
- Return ‘ANS’.
HELPER(‘MID’)
- Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’ and initialize it with 1. (First ugly number)
- Store the sum of the count of ugly numbers in ‘CNT’, which are multiple of 2, 3, and 5, by calling the function HELP1.
- Call the function HELP2 to find the count of ugly numbers till ‘MID’, which are multiples of both 2 and 3, 3 and 5, and 2 and 5, and update the ‘CNT’.
- Similarly, call function HELP3 to store the count of ugly numbers till ‘MID’, which are multiples of 2, 3, and 5.
- Return ‘CNT’.
HELP1(‘MID’, ‘VAL’) (where ‘VAl’ is multiple)
- Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’.
- Run a loop till ‘MID’ is greater than equal to ‘VAL’.
- Increment ‘CNT’ by 1.
- Update ‘MID’ by ‘MID’ / ‘VAL’.
- Return ‘CNT’.
HELP2(‘MID’, ‘VAL1’, ‘VAL2’) (where ‘VAl1’ and ‘VAL2’ are multiples)
- Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’.
- Run a loop till ‘MID’ is greater than equal to ‘VAL’.
- Update ‘MID’ by ‘MID’ / ‘VAL1’.
- Increment ‘CNT’ by the value returned by function HELP1(‘MID’, ‘VAL2’)
- Return ‘CNT’.
HELP3(‘MID’, ‘VAL1’, ‘VAL2’, ‘VAL3’) (where ‘VAL1’, ‘VAL2’, and ‘VAL3’ are multiples)
- Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’.
- Run a loop till ‘MID’ is greater than equal to ‘VAL’.
- Update ‘MID’ by ‘MID’ / ‘VAL1’.
- Increment ‘CNT’ by the value returned by function HELP1(‘MID’, ‘VAL2’, ‘VAL3’)
- Return ‘CNT’.
The basic idea is to store the multiples of the 2, 3, and 5 to find the ‘Nth’ ugly number. We create an array (say, ‘DP’) and find all the ugly numbers until ‘N’. We find the multiples of 2, 3, and 5 choose the minimum as ‘ith’ ugly number where 1 <= i <= N.
For example:
Initially, 1st ugly number is: 1
Potential next ugly numbers can be 1 * 2, 1 * 3, 1 * 5
We choose a minimum out of these for the next ugly number, i.e., 2.
To find the next ugly number, we take a minimum of 2 * 2, 1 * 3, 1 * 5, which will be 3.
Similarly, we find the ‘Nth’ ugly number.
Here is the algorithm :
- Create an array (say, ‘DP’) of size ‘N’, to store the ugly numbers till ‘N’ and initialize ‘DP[0]’ with 1.
- Create three variables (say, ‘MUL2’, ‘MUL3’, ‘MUL5’) to point to the value stored at that index to get the next ugly number for multiple of 2, 3, and 5, respectively, and initialize them with 0.
- Create a variable (say, ‘NXT’) to store the next ugly number and initialize it with 1.
- Run a loop from 1 to ‘N’ (say, iterator ’i’)
- Update ‘NXT’ by a minimum of ‘NXT2’, ‘NXT3’, and ‘NXT5’.
- Update ‘DP[i]’ with ‘NXT’.
- Check if ‘NXT’ is equal to 2 * ‘DP[MUL2]’.
- Increment ‘MUL2’ by 1.
- Similarly, check for multiples of 3 and 5, and update ‘MUL3’, and ‘MUL5’.
- Return ‘NXT’.