Los números feos son números cuyos únicos factores primos son 2, 3 o 5. La secuencia 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,… muestra los primeros 11 números feos. Por convención, 1 está incluido.
Dado un número n, la tarea es encontrar el n’ésimo número feo.
Ejemplos:
Input : n = 7 Output : 8 Input : n = 10 Output : 12 Input : n = 15 Output : 24 Input : n = 150 Output : 5832
Método 1 (Simple)
Bucle para todos los enteros positivos hasta que el conteo de números feos sea menor que n, si un entero es feo, entonces incremente el conteo de números feos.
Para verificar si un número es feo, divida el número por las mayores potencias divisibles de 2, 3 y 5, si el número se convierte en 1, entonces es un número feo, de lo contrario no lo es.
Por ejemplo, veamos cómo verificar si 300 es feo o no. El mayor poder divisible de 2 es 4, después de dividir 300 entre 4 obtenemos 75. El mayor poder divisible de 3 es 3, luego de dividir 75 entre 3 obtenemos 25. El mayor poder divisible de 5 es 25, después de dividir 25 entre 25 obtenemos 1 Como finalmente obtenemos 1, 300 es un número feo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find nth ugly number
#include <iostream>
using namespace std;
// This function divides a by greatest
// divisible power of b
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
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
int 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 Code
int 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 b
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
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
int 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 Code
int main()
{
// Function call
unsigned no = getNthUglyNo(150);
printf("150th ugly no. is %d ", no);
getchar();
return 0;
}
Java
// Java program to find nth ugly number
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 b
def maxDivide(a, b):
while a % b == 0:
a = a / b
return a
# Function to check if a number
# is ugly or not
def 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 number
def 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 code
no = getNthUglyNo(150)
print("150th ugly no. is ", no)
# This code is contributed by "Sharad_Bhardwaj".
C#
// C# program to find nth ugly number
using 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 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)
{
$i = 1;
// ugly number count
$count = 1;
// Check for all integers
// until ugly count becomes n
while ($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>
Producción
150th ugly no. is 5832
Este método no es eficiente en el tiempo ya que verifica todos los números enteros hasta que el conteo de números feos se convierte en n, pero la complejidad del espacio de este método es O (1)
Método 2 (Usar programación dinámica)
Aquí hay una solución eficiente en el tiempo con O (n) espacio adicional . La secuencia de números feos es 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
porque cada número solo se puede dividir por 2, 3, 5, una forma de ver la secuencia. es dividir la secuencia en tres grupos de la siguiente manera:
(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, …
Podemos encontrar que cada subsecuencia es la secuencia fea en sí misma (1, 2, 3, 4, 5, …) multiplicar 2, 3, 5. Luego usamos un método de combinación similar al ordenamiento por combinación, para obtener cada número feo de los tres subsecuencias. En cada paso elegimos el más pequeño y avanzamos un paso después.
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
Ejemplo:
Veamos cómo funciona
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 number
unsigned 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 Code
int 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 number
unsigned 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 Code
int 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 number
import java.lang.Math;
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 number def 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 Code def 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 array
using 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 number
function 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 code
var n = 150;
// Function call
document.write(getNthUglyNo(n));
// This code is contributed by Amit Katiyar
</script>
Producción
5832
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Número súper feo (Número cuyos factores primos están en el conjunto dado)
Método 3 (usando la estructura de datos SET en C++, Javascript y TreeSet en JAVA)
En este método, SET estructura de datos para almacenar el mínimo de los 3 números feos generados que serán el i -ésimo Número feo almacenado en la primera posición del conjunto. SET Estructura de datos como un conjunto almacena todos los elementos en orden ascendente
A continuación se muestra la implementación del enfoque anterior:
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 Code
int 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 approach def 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 Code n = 150 # Function call print( 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>
Producción
5832
Complejidad de tiempo:- O(N log N)
Espacio auxiliar:- O(N)
Método 4 (usando la búsqueda binaria)
- Este método es adecuado si tiene un valor máximo para n. El no será de la forma x=pow(2,p)*pow(3,q)*pow(5,r).
- Busque desde bajo = 1 hasta alto = 21474836647. Esperamos que el enésimo feo no esté en este rango.
- Así que hacemos una búsqueda binaria. Ahora supongamos que estamos en la mitad, ahora vamos a encontrar el número total de números feos menor que la mitad y pondremos nuestras condiciones en consecuencia.
A continuación se muestra el código CPP aproximado:
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Print nth Ugly number
int 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 Code
int main()
{
int n = 150;
// Function Call
cout << nthUglyNumber(n);
return 0;
}
Java
// JAVA program for the above approach
import java.util.*;
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 approach def 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 number def 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 Code n = 150 # Function Call print(nthUglyNumber(n)) # This code is contributed by code_hunt.
C#
// C# program for the above approach
using 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>
Producción
5832
Complejidad de tiempo: O (log N)
Espacio Auxiliar: O(1)
Escriba comentarios si encuentra algún error en el programa anterior u otras formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA