Dada una array de n enteros. La tarea es encontrar el número más grande que no sea un cubo perfecto. Imprime -1 si no hay ningún número que sea un cubo perfecto.
Ejemplos :
Input: arr[] = {16, 8, 25, 2, 3, 10}
Output: 25
25 is the largest number that is not a perfect cube.
Input: arr[] = {36, 64, 10, 16, 29, 25}
Output: 36
Una solución simple es ordenar los elementos y luego ordenar los números y comenzar a buscar desde atrás un número de cubo no perfecto usando la función cbrt(). El primer número desde el final que no es un número cúbico perfecto es nuestra respuesta. La complejidad de clasificación es O(n log n) y de la función cbrt() es log n, por lo que en el peor de los casos, la complejidad es O(n log n).
Una solución eficiente es iterar para todos los elementos en O(n) y comparar cada vez con el elemento máximo y almacenar el máximo de todos los cubos no perfectos.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the largest non-perfect
// cube number among n numbers
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number
// is perfect cube number or not
bool checkPerfectcube(int n)
{
// takes the sqrt of the number
int d = cbrt(n);
// checks if it is a perfect
// cube number
if (d * d * d == n)
return true;
return false;
}
// Function to find the largest non perfect
// cube number in the array
int largestNonPerfectcubeNumber(int a[], int n)
{
// stores the maximum of all
// perfect cube numbers
int maxi = -1;
// Traverse all elements in the array
for (int i = 0; i < n; i++) {
// store the maximum if current
// element is a non perfect cube
if (!checkPerfectcube(a[i]))
maxi = max(a[i], maxi);
}
return maxi;
}
// Driver Code
int main()
{
int a[] = { 16, 64, 25, 2, 3, 10 };
int n = sizeof(a) / sizeof(a[0]);
cout << largestNonPerfectcubeNumber(a, n);
return 0;
}
C
// C program to find the largest non-perfect
// cube number among n numbers
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
int max(int a, int b)
{
int max = a;
if(max < b)
max = b;
return max;
}
// Function to check if a number
// is perfect cube number or not
bool checkPerfectcube(int n)
{
// takes the sqrt of the number
int d = cbrt(n);
// checks if it is a perfect
// cube number
if (d * d * d == n)
return true;
return false;
}
// Function to find the largest non perfect
// cube number in the array
int largestNonPerfectcubeNumber(int a[], int n)
{
// stores the maximum of all
// perfect cube numbers
int maxi = -1;
// Traverse all elements in the array
for (int i = 0; i < n; i++) {
// store the maximum if current
// element is a non perfect cube
if (!checkPerfectcube(a[i]))
maxi = max(a[i], maxi);
}
return maxi;
}
// Driver Code
int main()
{
int a[] = { 16, 64, 25, 2, 3, 10 };
int n = sizeof(a) / sizeof(a[0]);
printf("%d",largestNonPerfectcubeNumber(a, n));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to find the largest non-perfect
// cube number among n numbers
import java.io.*;
class GFG {
// Function to check if a number
// is perfect cube number or not
static boolean checkPerfectcube(int n)
{
// takes the sqrt of the number
int d = (int)Math.cbrt(n);
// checks if it is a perfect
// cube number
if (d * d * d == n)
return true;
return false;
}
// Function to find the largest non perfect
// cube number in the array
static int largestNonPerfectcubeNumber(int []a, int n)
{
// stores the maximum of all
// perfect cube numbers
int maxi = -1;
// Traverse all elements in the array
for (int i = 0; i < n; i++) {
// store the maximum if current
// element is a non perfect cube
if (!checkPerfectcube(a[i]))
maxi = Math.max(a[i], maxi);
}
return maxi;
}
// Driver Code
public static void main (String[] args) {
int a[] = { 16, 64, 25, 2, 3, 10 };
int n = a.length;
System.out.print( largestNonPerfectcubeNumber(a, n));
}
}
// This code is contributed
// by inder_verma
Python 3
# Python 3 program to find the largest # non-perfect cube number among n numbers import math # Function to check if a number # is perfect cube number or not def checkPerfectcube(n): # takes the sqrt of the number cube_root = n ** (1./3.) if round(cube_root) ** 3 == n: return True else: return False # Function to find the largest non # perfect cube number in the array def largestNonPerfectcubeNumber(a, n): # stores the maximum of all # perfect cube numbers maxi = -1 # Traverse all elements in the array for i in range(0, n, 1): # store the maximum if current # element is a non perfect cube if (checkPerfectcube(a[i]) == False): maxi = max(a[i], maxi) return maxi # Driver Code if __name__ == '__main__': a = [16, 64, 25, 2, 3, 10] n = len(a) print(largestNonPerfectcubeNumber(a, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find the largest non-perfect
// cube number among n numbers
using System;
public class GFG {
// Function to check if a number
// is perfect cube number or not
static bool checkPerfectcube(int n)
{
// takes the sqrt of the number
int d = (int)Math.Ceiling(Math.Pow(n, (double)1 / 3));
// checks if it is a perfect
// cube number
if (d * d * d == n)
return true;
return false;
}
// Function to find the largest non perfect
// cube number in the array
static int largestNonPerfectcubeNumber(int []a, int n)
{
// stores the maximum of all
// perfect cube numbers
int maxi = -1;
// Traverse all elements in the array
for (int i = 0; i < n; i++) {
// store the maximum if current
// element is a non perfect cube
if (checkPerfectcube(a[i])==false)
maxi = Math.Max(a[i], maxi);
}
return maxi;
}
// Driver Code
public static void Main () {
int []a = { 16, 64, 25, 2, 3, 10 };
int n = a.Length;
Console.WriteLine( largestNonPerfectcubeNumber(a, n));
}
}
/*This code is contributed by PrinciRaj1992*/
PHP
<?php
// PHP program to find the largest non-perfect
// cube number among n numbers
// Function to check if a number
// is perfect cube number or not
function checkPerfectcube($n)
{
// takes the sqrt of the number
$d = (int)round(pow($n, 1/3));
// checks if it is a perfect
// cube number
if ($d * $d * $d == $n)
return true;
return false;
}
// Function to find the largest non perfect
// cube number in the array
function largestNonPerfectcubeNumber($a, $n)
{
// stores the maximum of all
// perfect cube numbers
$maxi = -1;
// Traverse all elements in the array
for ($i = 0; $i < $n; $i++) {
// store the maximum if current
// element is a non perfect cube
if (!checkPerfectcube($a[$i]))
$maxi = max($a[$i], $maxi);
}
return $maxi;
}
// Driver Code
$a = array( 16, 64, 25, 2, 3, 10 );
$n = count($a);
echo largestNonPerfectcubeNumber($a, $n);
// this code is contributed by mits
?>
Javascript
<script>
// Javascript program to find the largest non-perfect
// cube number among n numbers
// Function to check if a number
// is perfect cube number or not
function checkPerfectcube(n)
{
// takes the sqrt of the number
let d = Math.cbrt(n);
// checks if it is a perfect
// cube number
if (d * d * d == n)
return true;
return false;
}
// Function to find the largest non perfect
// cube number in the array
function largestNonPerfectcubeNumber(a, n)
{
// stores the maximum of all
// perfect cube numbers
let maxi = -1;
// Traverse all elements in the array
for (let i = 0; i < n; i++) {
// store the maximum if current
// element is a non perfect cube
if (!checkPerfectcube(a[i]))
maxi = Math.max(a[i], maxi);
}
return maxi;
}
// Driver Code
let a = [ 16, 64, 25, 2, 3, 10 ];
let n = a.length;
document.write(largestNonPerfectcubeNumber(a, n));
// This code is contributed by souravmahato348.
</script>
Producción:
25
Complejidad de tiempo: O (nlog 3 (val)), ya que se ejecuta un ciclo de 0 a (n – 1) donde val es el valor máximo de la array.
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA