Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1 is included.
Given a number n, the task is to find n’th Ugly number.
Examples:
Input : n = 7 Output : 8 Input : n = 10 Output : 12 Input : n = 15 Output : 24 Input : n = 150 Output : 5832
Method 1 (Simple)
Loop for all positive integers till the ugly number count is smaller than n, if an integer is ugly then increment ugly number count.
To check 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.
For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.
Below is the implementation of the above approach:
C++
// C++ program to find nth ugly number#include <iostream>using namespace std;// This function divides a by greatest// divisible power of bint maxDivide(int a, int b){ while (a % b == 0) a = a / b; return a;}// Function to check if a number is ugly or notint isUgly(int no){ no = maxDivide(no, 2); no = maxDivide(no, 3); no = maxDivide(no, 5); return (no == 1) ? 1 : 0;}// Function to get the nth ugly numberint getNthUglyNo(int n){ int i = 1; // Ugly number count int count = 1; // Check for all integers until ugly // count becomes n while (n > count) { i++; if (isUgly(i)) count++; } return i;}// Driver Codeint main(){ // Function call unsigned no = getNthUglyNo(150); cout << "150th ugly no. is " << no; return 0;}// This code is contributed by shivanisinghss2110 |
C
// C program to find nth ugly number#include <stdio.h>#include <stdlib.h>// This function divides a by greatest divisible// power of bint maxDivide(int a, int b){ while (a % b == 0) a = a / b; return a;}// Function to check if a number is ugly or notint isUgly(int no){ no = maxDivide(no, 2); no = maxDivide(no, 3); no = maxDivide(no, 5); return (no == 1) ? 1 : 0;}// Function to get the nth ugly numberint getNthUglyNo(int n){ int i = 1; // ugly number count int count = 1; // Check for all integers until ugly count // becomes n while (n > count) { i++; if (isUgly(i)) count++; } return i;}// Driver Codeint main(){ // Function call unsigned no = getNthUglyNo(150); printf("150th ugly no. is %d ", no); getchar(); return 0;} |
Java
// Java program to find nth ugly numberimport java.io.*;public class GFG { /*This function divides a by greatest divisible power of b*/ static int maxDivide(int a, int b) { while (a % b == 0) a = a / b; return a; } /* Function to check if a number is ugly or not */ static int isUgly(int no) { no = maxDivide(no, 2); no = maxDivide(no, 3); no = maxDivide(no, 5); return (no == 1) ? 1 : 0; } /* Function to get the nth ugly number*/ static int getNthUglyNo(int n) { int i = 1; // ugly number count int count = 1; // check for all integers // until count becomes n while (n > count) { i++; if (isUgly(i) == 1) count++; } return i; } /* Driver Code*/ public static void main(String args[]) { int no = getNthUglyNo(150); // Function call System.out.println("150th ugly " + "no. is " + no); }}// This code has been contributed by// Amit Khandelwal (Amit Khandelwal 1) |
Python3
# Python3 code to find nth ugly number# This function divides a by greatest# divisible power of bdef maxDivide(a, b): while a % b == 0: a = a / b return a# Function to check if a number# is ugly or notdef isUgly(no): no = maxDivide(no, 2) no = maxDivide(no, 3) no = maxDivide(no, 5) return 1 if no == 1 else 0# Function to get the nth ugly numberdef getNthUglyNo(n): i = 1 # ugly number count count = 1 # Check for all integers until # ugly count becomes n while n > count: i += 1 if isUgly(i): count += 1 return i# Driver codeno = getNthUglyNo(150)print("150th ugly no. is ", no)# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to find nth ugly numberusing System;class GFG { /*This function divides a by greatest divisible power of b*/ static int maxDivide(int a, int b) { while (a % b == 0) a = a / b; return a; } /* Function to check if a number is ugly or not */ static int isUgly(int no) { no = maxDivide(no, 2); no = maxDivide(no, 3); no = maxDivide(no, 5); return (no == 1) ? 1 : 0; } /* Function to get the nth ugly number*/ static int getNthUglyNo(int n) { int i = 1; // ugly number count int count = 1; // Check for all integers // until count becomes n while (n > count) { i++; if (isUgly(i) == 1) count++; } return i; } // Driver code public static void Main() { int no = getNthUglyNo(150); // Function call Console.WriteLine("150th ugly" + " no. is " + no); }}// This code is contributed by Sam007. |
PHP
<?php// PHP program to find nth ugly number// This function divides a by // greatest divisible power of bfunction maxDivide($a, $b){ while ($a % $b == 0) $a = $a / $b; return $a;} // Function to check if a // number is ugly or not function isUgly($no){ $no = maxDivide($no, 2); $no = maxDivide($no, 3); $no = maxDivide($no, 5); return ($no == 1)? 1 : 0;} // Function to get the nth// ugly numberfunction getNthUglyNo($n){ $i = 1; // ugly number count $count = 1; // Check for all integers // until ugly count becomes nwhile ($n > $count){ $i++; if (isUgly($i)) $count++; }return $i;} // Driver Code $no = getNthUglyNo(150); echo "150th ugly no. is ". $no;// This code is contributed by Sam007?> |
Javascript
<script>// javascript program to find nth ugly number /* * This function divides a by greatest divisible power of b */ function maxDivide(a , b) { while (a % b == 0) a = a / b; return a; } /* * Function to check if a number is ugly or not */ function isUgly(no) { no = maxDivide(no, 2); no = maxDivide(no, 3); no = maxDivide(no, 5); return (no == 1) ? 1 : 0; } /* * Function to get the nth ugly number */ function getNthUglyNo(n) { var i = 1; // ugly number count var count = 1; // check for all integers // until count becomes n while (n > count) { i++; if (isUgly(i) == 1) count++; } return i; } /* Driver Code */ var no = getNthUglyNo(150); // Function call document.write("150th ugly " + "no. is " + no);// This code is contributed by shikhasingrajput </script> |
Output
150th ugly no. is 5832
This method is not time efficient as it checks for all integers until ugly number count becomes n, but 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 to three groups as below:
(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …
We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5. Then we use similar merge method as merge sort, to get every ugly number from the three subsequences. Every step we choose the smallest one, and move one step after.
1 Declare an array for ugly numbers: ugly[n]
2 Initialize first ugly no: ugly[0] = 1
3 Initialize three array index variables i2, i3, i5 to point to
1st element of the ugly array:
i2 = i3 = i5 =0;
4 Initialize 3 choices for the next ugly no:
next_multiple_of_2 = ugly[i2]*2;
next_multiple_of_3 = ugly[i3]*3
next_multiple_of_5 = ugly[i5]*5;
5 Now go in a loop to fill all ugly numbers till 150:
For (i = 1; i < 150; i++ )
{
/* These small steps are not optimized for good
readability. Will optimize them in C program */
next_ugly_no = Min(next_multiple_of_2,
next_multiple_of_3,
next_multiple_of_5);
ugly[i] = next_ugly_no
if (next_ugly_no == next_multiple_of_2)
{
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2]*2;
}
if (next_ugly_no == next_multiple_of_3)
{
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3]*3;
}
if (next_ugly_no == next_multiple_of_5)
{
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5]*5;
}
}/* end of for loop */
6.return next_ugly_no
Example:
Let us see how it works
initialize
ugly[] = | 1 |
i2 = i3 = i5 = 0;
First iteration
ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(2, 3, 5)
= 2
ugly[] = | 1 | 2 |
i2 = 1, i3 = i5 = 0 (i2 got incremented )
Second iteration
ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(4, 3, 5)
= 3
ugly[] = | 1 | 2 | 3 |
i2 = 1, i3 = 1, i5 = 0 (i3 got incremented )
Third iteration
ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(4, 6, 5)
= 4
ugly[] = | 1 | 2 | 3 | 4 |
i2 = 2, i3 = 1, i5 = 0 (i2 got incremented )
Fourth iteration
ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(6, 6, 5)
= 5
ugly[] = | 1 | 2 | 3 | 4 | 5 |
i2 = 2, i3 = 1, i5 = 1 (i5 got incremented )
Fifth iteration
ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(6, 6, 10)
= 6
ugly[] = | 1 | 2 | 3 | 4 | 5 | 6 |
i2 = 3, i3 = 2, i5 = 1 (i2 and i3 got incremented )
Will continue same way till I < 150
C++
// C++ program to find n'th Ugly number#include <bits/stdc++.h>using namespace std;// Function to get the nth ugly numberunsigned getNthUglyNo(unsigned n){ // To store ugly numbers unsigned ugly[n]; unsigned i2 = 0, i3 = 0, i5 = 0; unsigned next_multiple_of_2 = 2; unsigned next_multiple_of_3 = 3; unsigned next_multiple_of_5 = 5; unsigned next_ugly_no = 1; ugly[0] = 1; for (int i = 1; i < n; i++) { next_ugly_no = min( next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5)); ugly[i] = next_ugly_no; if (next_ugly_no == next_multiple_of_2) { i2 = i2 + 1; next_multiple_of_2 = ugly[i2] * 2; } if (next_ugly_no == next_multiple_of_3) { i3 = i3 + 1; next_multiple_of_3 = ugly[i3] * 3; } if (next_ugly_no == next_multiple_of_5) { i5 = i5 + 1; next_multiple_of_5 = ugly[i5] * 5; } } // End of for loop (i=1; i<n; i++) return next_ugly_no;}// Driver Codeint main(){ int n = 150; cout << getNthUglyNo(n); return 0;}// This code is contributed by Sania Kumari Gupta (kriSania804) |
C
// C program to find n'th Ugly number#include <stdio.h>// Find minimum between two numbers.int min(int num1, int num2){ return (num1 > num2) ? num2 : num1;}// Function to get the nth ugly numberunsigned getNthUglyNo(unsigned n){ // To store ugly numbers unsigned ugly[n]; unsigned i2 = 0, i3 = 0, i5 = 0; unsigned next_multiple_of_2 = 2; unsigned next_multiple_of_3 = 3; unsigned next_multiple_of_5 = 5; unsigned next_ugly_no = 1; ugly[0] = 1; for (int i = 1; i < n; i++) { next_ugly_no = min( next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5)); ugly[i] = next_ugly_no; if (next_ugly_no == next_multiple_of_2) { i2 = i2 + 1; next_multiple_of_2 = ugly[i2] * 2; } if (next_ugly_no == next_multiple_of_3) { i3 = i3 + 1; next_multiple_of_3 = ugly[i3] * 3; } if (next_ugly_no == next_multiple_of_5) { i5 = i5 + 1; next_multiple_of_5 = ugly[i5] * 5; } } // End of for loop (i=1; i<n; i++) return next_ugly_no;}// Driver Codeint main(){ int n = 150; printf("%u",getNthUglyNo(n)); return 0;}// This code is contributed by Sania Kumari Gupta (kriSania804) |
Java
// Java program to find nth ugly numberimport java.lang.Math;import java.io.*;class UglyNumber{ // Function to get the nth ugly number int getNthUglyNo(int n) { // To store ugly numbers int ugly[] = new int[n]; int i2 = 0, i3 = 0, i5 = 0; int next_multiple_of_2 = 2; int next_multiple_of_3 = 3; int next_multiple_of_5 = 5; int next_ugly_no = 1; ugly[0] = 1; for (int i = 1; i < n; i++) { next_ugly_no = Math.min(next_multiple_of_2, Math.min(next_multiple_of_3, next_multiple_of_5)); ugly[i] = next_ugly_no; if (next_ugly_no == next_multiple_of_2) { i2 = i2 + 1; next_multiple_of_2 = ugly[i2] * 2; } if (next_ugly_no == next_multiple_of_3) { i3 = i3 + 1; next_multiple_of_3 = ugly[i3] * 3; } if (next_ugly_no == next_multiple_of_5) { i5 = i5 + 1; next_multiple_of_5 = ugly[i5] * 5; } } // End of for loop (i=1; i<n; i++) return next_ugly_no; } // Driver code public static void main(String args[]) { int n = 150; // Function call UglyNumber obj = new UglyNumber(); System.out.println(obj.getNthUglyNo(n)); }}// This code has been contributed by Amit Khandelwal (Amit// Khandelwal 1) |
Python
# Python program to find n'th Ugly number# Function to get the nth ugly numberdef getNthUglyNo(n): ugly = [0] * n # To store ugly numbers # 1 is the first ugly number ugly[0] = 1 # i2, i3, i5 will indicate indices for # 2,3,5 respectively i2 = i3 = i5 = 0 # Set initial multiple value next_multiple_of_2 = 2 next_multiple_of_3 = 3 next_multiple_of_5 = 5 # Start loop to find value from # ugly[1] to ugly[n] for l in range(1, n): # Choose the min value of all # available multiples ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5) # Increment the value of index accordingly if ugly[l] == next_multiple_of_2: i2 += 1 next_multiple_of_2 = ugly[i2] * 2 if ugly[l] == next_multiple_of_3: i3 += 1 next_multiple_of_3 = ugly[i3] * 3 if ugly[l] == next_multiple_of_5: i5 += 1 next_multiple_of_5 = ugly[i5] * 5 # Return ugly[n] value return ugly[-1]# Driver Codedef main(): n = 150 print getNthUglyNo(n)if __name__ == '__main__': main()# This code is contributed by Neelam Yadav |
C#
// C# program to count inversions in an arrayusing System;using System.Collections.Generic;class GFG { // Function to get the nth ugly number static int getNthUglyNo(int n) { // To store ugly numbers int[] ugly = new int[n]; int i2 = 0, i3 = 0, i5 = 0; int next_multiple_of_2 = 2; int next_multiple_of_3 = 3; int next_multiple_of_5 = 5; int next_ugly_no = 1; ugly[0] = 1; for (int i = 1; i < n; i++) { next_ugly_no = Math.Min(next_multiple_of_2, Math.Min(next_multiple_of_3, next_multiple_of_5)); ugly[i] = next_ugly_no; if (next_ugly_no == next_multiple_of_2) { i2 = i2 + 1; next_multiple_of_2 = ugly[i2] * 2; } if (next_ugly_no == next_multiple_of_3) { i3 = i3 + 1; next_multiple_of_3 = ugly[i3] * 3; } if (next_ugly_no == next_multiple_of_5) { i5 = i5 + 1; next_multiple_of_5 = ugly[i5] * 5; } } return next_ugly_no; } // Driver code public static void Main() { int n = 150; // Function call Console.WriteLine(getNthUglyNo(n)); }}// This code is contributed by Sam007 |
PHP
<?php// PHP program to find // n'th Ugly number// Function to get the// nth ugly number function getNthUglyNo($n){ // To store ugly numbers $ugly = array_fill(0, $n, 0); $i2 = 0; $i3 = 0; $i5 = 0; $next_multiple_of_2 = 2; $next_multiple_of_3 = 3; $next_multiple_of_5 = 5; $next_ugly_no = 1; $ugly[0] = 1; for ($i = 1; $i < $n; $i++) { $next_ugly_no = min($next_multiple_of_2, min($next_multiple_of_3, $next_multiple_of_5)); $ugly[$i] = $next_ugly_no; if ($next_ugly_no == $next_multiple_of_2) { $i2 = $i2 + 1; $next_multiple_of_2 = $ugly[$i2] * 2; } if ($next_ugly_no == $next_multiple_of_3) { $i3 = $i3 + 1; $next_multiple_of_3 = $ugly[$i3] * 3; } if ($next_ugly_no == $next_multiple_of_5) { $i5 = $i5 + 1; $next_multiple_of_5 = $ugly[$i5] * 5; } } /*End of for loop (i=1; i<n; i++) */ return $next_ugly_no;}// Driver code$n = 150;echo getNthUglyNo($n);// This code is contributed by mits?> |
Javascript
<script>// javascript program to find nth ugly numberclass UglyNumber// Function to get the nth ugly numberfunction getNthUglyNo(n){ // To store ugly numbers var ugly = Array.from({length: n}, (_, i) => 0); var i2 = 0, i3 = 0, i5 = 0; var next_multiple_of_2 = 2; var next_multiple_of_3 = 3; var next_multiple_of_5 = 5; var next_ugly_no = 1; ugly[0] = 1; for (i = 1; i < n; i++) { next_ugly_no = Math.min(next_multiple_of_2, Math.min(next_multiple_of_3, next_multiple_of_5)); ugly[i] = next_ugly_no; if (next_ugly_no == next_multiple_of_2) { i2 = i2 + 1; next_multiple_of_2 = ugly[i2] * 2; } if (next_ugly_no == next_multiple_of_3) { i3 = i3 + 1; next_multiple_of_3 = ugly[i3] * 3; } if (next_ugly_no == next_multiple_of_5) { i5 = i5 + 1; next_multiple_of_5 = ugly[i5] * 5; } } // End of for loop (i=1; i<n; i++) return next_ugly_no;}// Driver codevar n = 150;// Function calldocument.write(getNthUglyNo(n));// This code is contributed by Amit Katiyar </script> |
Output
5832
Time Complexity: O(n)
Auxiliary Space: O(n)
Super Ugly Number (Number whose prime factors are in the given set)
Method 3 (Using SET Data Structure in C++, Javascript and TreeSet in JAVA)
In this method, SET data structure to store the minimum of the 3 generated ugly numbers which will the ith Ugly Number stored at the first position of the set. SET Data Structure as a set stores all the element in ascending order
Below is the implementation of the above approach:
C++
// C++ Implementation of the above approach#include <bits/stdc++.h>using namespace std;int nthUglyNumber(int n){ // Base cases... if (n == 1 or n == 2 or n == 3 or n == 4 or n == 5) return n; set<long long int> s; s.insert(1); n--; while (n) { auto it = s.begin(); // Get the beginning element of the set long long int x = *it; // Deleting the ith element s.erase(it); // Inserting all the other options s.insert(x * 2); s.insert(x * 3); s.insert(x * 5); n--; } // The top of the set represents the nth ugly number return *s.begin();}// Driver Codeint main(){ int n = 150; // Function call cout << nthUglyNumber(n);}// Contributed by:- Soumak Poddar |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { static long nthUglyNumber(int n) { TreeSet<Long> t = new TreeSet<>(); // Ugly number sequence starts with 1 t.add(1L); int i = 1; // when i==n we have the nth ugly number while (i < n) { // remove the ith ugly number and add back its // multiples of 2,3 and 5 back to the set long temp = t.pollFirst(); t.add(temp * 2); t.add(temp * 3); t.add(temp * 5); i++; // the first element of set is always the ith // ugly number } return t.pollFirst(); } public static void main(String[] args) { int n = 150; System.out.println(nthUglyNumber(n)); }}// Contributed by:- Saswata Halder |
Python3
# Python Implementation of the above approachdef nthUglyNumber(n): # Base cases... if (n == 1 or n == 2 or n == 3 or n == 4 or n == 5): return n s = [1] n-=1 while (n): it = s[0] # Get the beginning element of the set x = it # Deleting the ith element s = s[1:] s = set(s) # Inserting all the other options s.add(x * 2) s.add(x * 3) s.add(x * 5) s = list(s) s.sort() n -= 1 # The top of the set represents the nth ugly number return s[0]# Driver Coden = 150# Function callprint( nthUglyNumber(n))# This code is contributed by Shubham Singh |
C#
/*package whatever //do not write package name here */using System;using System.Linq;using System.Collections.Generic;public class GFG { static long nthUglyNumber(int n) { SortedSet<long> t = new SortedSet<long>(); // Ugly number sequence starts with 1 t.Add(1L); int i = 1; // when i==n we have the nth ugly number while (i < n) { // remove the ith ugly number and add back its // multiples of 2,3 and 5 back to the set long temp = t.FirstOrDefault(); t.Remove(temp); t.Add(temp * 2); t.Add(temp * 3); t.Add(temp * 5); i++; // the first element of set is always the ith // ugly number } return t.FirstOrDefault(); } public static void Main(String[] args) { int n = 150; Console.WriteLine(nthUglyNumber(n)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach // Print nth Ugly number function nthUglyNumber(n) { // Base cases... if (n == 1 || n == 2 || n == 3 || n == 4 || n == 5) { return n; } var s = [1]; n = n - 1; while(n) { var it = s[0]; //Get the beginning element of the set var x = it; // Deleting the ith element s = s.slice(1); s = new Set(s); //Inserting all the other options s.add(x * 2); s.add(x * 3); s.add(x * 5); s = Array.from(s); s.sort(function(a, b){return a - b}); n = n - 1; } // The top of the set represents the nth ugly number return s[0]; } // Driver Code var n = 150; // Function Call document.write(nthUglyNumber(n)); // This code is contributed by kothavvsaakash</script> |
Output
5832
Time Complexity:- O(N log N)
Auxiliary Space:- O(N)
Method 4(Using Binary Search)
- This method is suitable if you have a max value for n. The no will be of form x=pow(2,p)*pow(3,q)*pow(5,r).
- Search from low=1 to high =21474836647. We are expecting nth ugly no to be in this range.
- So we do a binary search. Now suppose we are at mid now we are going to find the total number of ugly numbers less than mid and put our conditions accordingly.
Below is the rough CPP code:
C++
// CPP program for the above approach#include <bits/stdc++.h>using namespace std;// Print nth Ugly numberint nthUglyNumber(int n){ int pow[40] = { 1 }; // stored powers of 2 from // pow(2,0) to pow(2,30) for (int i = 1; i <= 30; ++i) pow[i] = pow[i - 1] * 2; // Initialized low and high int l = 1, r = 2147483647; int ans = -1; // Applying Binary Search while (l <= r) { // Found mid int mid = l + ((r - l) / 2); // cnt stores total numbers of ugly // number less than mid int cnt = 0; // Iterate from 1 to mid for (long long i = 1; i <= mid; i *= 5) { // Possible powers of i less than mid is i for (long long j = 1; j * i <= mid; j *= 3) { // possible powers of 3 and 5 such that // their product is less than mid // using the power array of 2 (pow) we are // trying to find the max power of 2 such // that i*J*power of 2 is less than mid cnt += upper_bound(pow, pow + 31, mid / (i * j)) - pow; } } // If total numbers of ugly number // less than equal // to mid is less than n we update l if (cnt < n) l = mid + 1; // If total numbers of ugly number // less than equal to // mid is greater than n we update // r and ans simultaneously. else r = mid - 1, ans = mid; } return ans;}// Driver Codeint main(){ int n = 150; // Function Call cout << nthUglyNumber(n); return 0;} |
Java
// JAVA program for the above approachimport java.util.*;import java.io.*;class GFG{ static int upperBound(int[] a, int low, int high, int element) { while(low < high) { int middle = low + (high - low)/2; if(a[middle] > element) high = middle; else low = middle + 1; } return low; } // Print nth Ugly number static int nthUglyNumber(int n) { int pow[] = new int[40]; Arrays.fill(pow, 1); // stored powers of 2 from // Math.pow(2,0) to Math.pow(2,30) for (int i = 1; i <= 30; ++i) pow[i] = pow[i - 1] * 2; // Initialized low and high int l = 1, r = 2147483647; int ans = -1; // Applying Binary Search while (l <= r) { // Found mid int mid = l + ((r - l) / 2); // cnt stores total numbers of ugly // number less than mid int cnt = 0; // Iterate from 1 to mid for (long i = 1; i <= mid; i *= 5) { // Possible powers of i less than mid is i for (long j = 1; j * i <= mid; j *= 3) { // possible powers of 3 and 5 such that // their product is less than mid // using the power array of 2 (pow) we are // trying to find the max power of 2 such // that i*J*power of 2 is less than mid cnt += upperBound(pow,0, 31, (int)(mid / (i * j))); } } // If total numbers of ugly number // less than equal // to mid is less than n we update l if (cnt < n) l = mid + 1; // If total numbers of ugly number // less than equal to // mid is greater than n we update // r and ans simultaneously. else { r = mid - 1; ans = mid; } } return ans; } // Driver Code public static void main(String[] args) { int n = 150; // Function Call System.out.print(nthUglyNumber(n)); }}// This code is contributed by Rajput-Ji |
Python3
# Python Program to implement# the above approachdef upper_bound(a, low, high, element) : while(low < high) : middle = low + (high - low)//2 if(a[middle] > element) : high = middle else : low = middle + 1 return low# Print nth Ugly numberdef nthUglyNumber(n) : pow = [1] * 40 # stored powers of 2 from # pow(2,0) to pow(2,30) for i in range(1, 31): pow[i] = pow[i - 1] * 2 # Initialized low and high l = 1 r = 2147483647 ans = -1 # Applying Binary Search while (l <= r) : # Found mid mid = l + ((r - l) // 2) # cnt stores total numbers of ugly # number less than mid cnt = 0 # Iterate from 1 to mid i = 1 while(i <= mid) : # Possible powers of i less than mid is i j = 1 while(j * i <= mid) : # possible powers of 3 and 5 such that # their product is less than mid # using the power array of 2 (pow) we are # trying to find the max power of 2 such # that i*J*power of 2 is less than mid cnt += upper_bound(pow, 0, 31, mid // (i * j)) j *= 3 i *= 5 # If total numbers of ugly number # less than equal # to mid is less than n we update l if (cnt < n): l = mid + 1 # If total numbers of ugly number # less than equal to # mid is greater than n we update # r and ans simultaneously. else : r = mid - 1 ans = mid return ans# Driver Coden = 150 # Function Callprint(nthUglyNumber(n))# This code is contributed by code_hunt. |
C#
// C# program for the above approachusing System;public class GFG { static int upperBound(int[] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2; if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Print nth Ugly number static int nthUglyNumber(int n) { int []pow = new int[40]; for (int i = 0; i <40; ++i) pow[i] = 1; // stored powers of 2 from // Math.Pow(2,0) to Math.Pow(2,30) for (int i = 1; i <= 30; ++i) pow[i] = pow[i - 1] * 2; // Initialized low and high int l = 1, r = 2147483647; int ans = -1; // Applying Binary Search while (l <= r) { // Found mid int mid = l + ((r - l) / 2); // cnt stores total numbers of ugly // number less than mid int cnt = 0; // Iterate from 1 to mid for (long i = 1; i <= mid; i *= 5) { // Possible powers of i less than mid is i for (long j = 1; j * i <= mid; j *= 3) { // possible powers of 3 and 5 such that // their product is less than mid // using the power array of 2 (pow) we are // trying to find the max power of 2 such // that i*J*power of 2 is less than mid cnt += upperBound(pow, 0, 31, (int) (mid / (i * j))); } } // If total numbers of ugly number // less than equal // to mid is less than n we update l if (cnt < n) l = mid + 1; // If total numbers of ugly number // less than equal to // mid is greater than n we update // r and ans simultaneously. else { r = mid - 1; ans = mid; } } return ans; } // Driver Code public static void Main(String[] args) { int n = 150; // Function Call Console.Write(nthUglyNumber(n)); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program for the above approach function upperBound(a , low , high , element) { while (low < high) { var middle = low + parseInt((high - low) / 2); if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Print nth Ugly number function nthUglyNumber(n) { var pow = Array(40).fill(1); // stored powers of 2 from // Math.pow(2,0) to Math.pow(2,30) for (i = 1; i <= 30; ++i) pow[i] = pow[i - 1] * 2; // Initialized low and high var l = 1, r = 2147483647; var ans = -1; // Applying Binary Search while (l <= r) { // Found mid var mid = l + parseInt((r - l) / 2); // cnt stores total numbers of ugly // number less than mid var cnt = 0; // Iterate from 1 to mid for (i = 1; i <= mid; i *= 5) { // Possible powers of i less than mid is i for (j = 1; j * i <= mid; j *= 3) { // possible powers of 3 and 5 such that // their product is less than mid // using the power array of 2 (pow) we are // trying to find the max power of 2 such // that i*J*power of 2 is less than mid cnt += upperBound(pow, 0, 31, parseInt( (mid / (i * j)))); } } // If total numbers of ugly number // less than equal // to mid is less than n we update l if (cnt < n) l = mid + 1; // If total numbers of ugly number // less than equal to // mid is greater than n we update // r and ans simultaneously. else { r = mid - 1; ans = mid; } } return ans; } // Driver Code var n = 150; // Function Call document.write(nthUglyNumber(n));// This code is contributed by gauravrajput1</script> |
Output
5832
Time Complexity: O(log N)
Auxiliary Space: O(1)
Please write comments if you find any bug in the above program or other ways to solve the same problem.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
