El cubo perfecto más pequeño de una array

Dada una array arr[] de n enteros. La tarea es encontrar el cubo perfecto más pequeño de la array. Imprime -1 si no hay un cubo perfecto en la array.
Ejemplos: 
 

Entrada: arr[] = {16, 8, 25, 2, 3, 10} 
Salida: 8 
8 es el único cubo perfecto en la array
Entrada: arr[] = {27, 8, 1, 64} 
Salida: 1 
Todo los elementos son cubos perfectos pero 1 es el mínimo de todos. 
 

Una solución simple es ordenar los elementos y luego ordenar los números y comenzar a buscar desde el principio un número de cubo perfecto usando la función cbrt() . El primer número desde el principio, que 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 por todos los elementos en O(n) y comparar cada vez con el elemento mínimo y almacenar el mínimo de todos los cubos perfectos.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true
// if n is a perfect cube
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 return the smallest perfect
// cube from the array
int smallestPerfectCube(int a[], int n)
{
 
    // Stores the minimum of all the
    // perfect cubes from the array
    int mini = INT_MAX;
 
    // Traverse all elements in the array
    for (int i = 0; i < n; i++) {
 
        // Store the minimum if current
        // element is a perfect cube
        if (checkPerfectcube(a[i])) {
            mini = min(a[i], mini);
        }
    }
 
    return mini;
}
 
// Driver code
int main()
{
    int a[] = { 16, 8, 25, 2, 3, 10 };
 
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << smallestPerfectCube(a, n);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
// Function that returns true
// if n is a perfect cube
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 return the smallest perfect
// cube from the array
static int smallestPerfectCube(int a[], int n)
{
 
    // Stores the minimum of all the
    // perfect cubes from the array
    int mini = Integer.MAX_VALUE;
 
    // Traverse all elements in the array
    for (int i = 0; i < n; i++)
    {
 
        // Store the minimum if current
        // element is a perfect cube
        if (checkPerfectcube(a[i]))
        {
            mini = Math.min(a[i], mini);
        }
    }
 
    return mini;
}
 
// Driver code
public static void main (String[] args)
{
    int a[] = { 16, 8, 25, 2, 3, 10 };
 
    int n = a.length;
 
    System.out.print(smallestPerfectCube(a, n));
}
}
 
// This code is contributed by anuj_67..

# Python3 implementation of the approach
 
import sys
 
# Function that returns true
# if n is a perfect cube
def checkPerfectcube(n) :
     
    # Takes the sqrt of the number
    d = int(n**(1/3));
 
    # Checks if it is a perfect
    # cube number
    if (d * d * d == n) :
        return True;
 
    return False;
 
# Function to return the smallest perfect
# cube from the array
def smallestPerfectCube(a, n) :
 
    # Stores the minimum of all the
    # perfect cubes from the array
    mini = sys.maxsize;
 
    # Traverse all elements in the array
    for i in range(n) :
 
        # Store the minimum if current
        # element is a perfect cube
        if (checkPerfectcube(a[i])) :
            mini = min(a[i], mini);
             
    return mini;
 
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 16, 8, 25, 2, 3, 10 ];
 
    n = len(a);
 
    print(smallestPerfectCube(a, n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function that returns true
    // if n is a perfect cube
    static bool checkPerfectcube(int n)
    {
        // Takes the sqrt of the number
        int d = (int)Math.Sqrt(n);
     
        // Checks if it is a perfect
        // cube number
        if (d * d * d == n)
            return true;
     
        return false;
    }
     
    // Function to return the smallest perfect
    // cube from the array
    static int smallestPerfectCube(int []a, int n)
    {
     
        // Stores the minimum of all the
        // perfect cubes from the array
        int mini = int.MaxValue;
     
        // Traverse all elements in the array
        for (int i = 0; i < n; i++)
        {
     
            // Store the minimum if current
            // element is a perfect cube
            if (checkPerfectcube(a[i]))
            {
                mini = Math.Min(a[i], mini);
            }
        }
     
        return mini;
    }
     
    // Driver code
    static public void Main ()
    {
        int []a = { 16, 8, 25, 2, 3, 10 };
     
        int n = a.Length;
        Console.Write(smallestPerfectCube(a, n));
    }
}
 
// This code is contributed by ajit..

<script>
 
// Javascript implementation of the approach
 
// Function that returns true
// if n is a perfect cube
function checkPerfectcube(n)
{
    // Takes the sqrt of the number
    let d = parseInt(Math.cbrt(n));
 
    // Checks if it is a perfect
    // cube number
    if (d * d * d == n)
        return true;
 
    return false;
}
 
// Function to return the smallest perfect
// cube from the array
function smallestPerfectCube(a, n)
{
 
    // Stores the minimum of all the
    // perfect cubes from the array
    let mini = Number.MAX_VALUE;
 
    // Traverse all elements in the array
    for (let i = 0; i < n; i++) {
 
        // Store the minimum if current
        // element is a perfect cube
        if (checkPerfectcube(a[i])) {
            mini = Math.min(a[i], mini);
        }
    }
 
    return mini;
}
 
// Driver code
let a = [ 16, 8, 25, 2, 3, 10 ];
 
let n = a.length;
 
document.write(smallestPerfectCube(a, n));
 
</script>

8

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)