Ugly Numbers

Moderate
0/80
profile
Contributed by
7 upvotes
Asked in companies
Goldman SachsGameskraftServiceNow

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
10
1
Sample Output 1 :
12
1
Explanation For Sample Input 1 :
For the first test case :
The 10th ugly number is 12.

For the second test :
The 1st ugly number is 1.
Sample Input 2 :
2
15
150
Sample Output 2 :
24
5832
Hint

Try to find the count of ugly numbers less than a number.

Approaches (2)
Binary Search Approach

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 :

 

  1. Create a variable (say, ‘ANS’) used to store the result.
  2. Initialize a range (say, ‘LOW’ and ‘HIGH’) where the result will lie.
  3. 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.
  4. Return ‘ANS’.

 

HELPER(‘MID’) 
 

  1. Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’ and initialize it with 1. (First ugly number)
  2. Store the sum of the count of ugly numbers in ‘CNT’, which are multiple of 2, 3, and 5, by calling the function HELP1.
  3. 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’.
  4. Similarly, call function HELP3 to store the count of ugly numbers till ‘MID’, which are multiples of 2, 3, and 5.
  5. Return ‘CNT’.
     

HELP1(‘MID’, ‘VAL’)   (where ‘VAl’ is multiple)
 

  1. Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’.
  2. Run a loop till ‘MID’ is greater than equal to ‘VAL’.
    • Increment ‘CNT’ by 1.
    • Update ‘MID’ by ‘MID’ / ‘VAL’.
  3. Return ‘CNT’.

 

HELP2(‘MID’, ‘VAL1’, ‘VAL2’)   (where ‘VAl1’ and ‘VAL2’ are multiples)

 

  1. Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’.
  2. 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’)
  3. Return ‘CNT’.

 

HELP3(‘MID’, ‘VAL1’, ‘VAL2’, ‘VAL3’)   (where ‘VAL1’, ‘VAL2’, and ‘VAL3’ are multiples)
 

  1. Create a variable (say, ‘CNT’) to count the ugly numbers till ‘MID’.
  2. 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’)
  3. Return ‘CNT’.
Time Complexity

O((log(10^18))^4)

 

We use binary search to find the number having a count of ugly numbers smaller than ‘N’, which takes O(log(10^18)) time, and finding count of the ugly numbers smaller than a number that takes O(log(10^18)^3) time. Therefore, the overall time complexity will be O(log(10^18)^4), i.e., O(1).

Space Complexity

O(log(10^18))

 

The recursive stack to count the ugly numbers smaller than ‘N’ can have O(log(10^18)) space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Ugly Numbers
Full screen
Console