Dados n enteros, encuentre el número más grande que no sea un cuadrado perfecto. Escribe -1 si no hay ningún número que sea cuadrado perfecto.
Ejemplos:
Input : arr[] = {16, 20, 25, 2, 3, 10|
Output : 20
Explanation: 20 is the largest number
that is not a perfect square
Input : arr[] = {36, 64, 10, 16, 29, 25|
Output : 29
Una solución normal es ordenar los elementos y ordenar los n números y comenzar a buscar desde atrás un número cuadrado no perfecto usando la función sqrt(). El primer número desde el final que no es un número cuadrado perfecto es nuestra respuesta. La complejidad de clasificación es O(n log n) y de la función sqrt() es log n, por lo que en el peor de los casos la complejidad es O(n log n log n).
La solución eficiente es iterar para todos los elementos usando el recorrido en O(n) y comparar cada vez con el elemento máximo, y almacenar el máximo de todos los cuadrados no perfectos. El número almacenado en máximo será nuestra respuesta.
A continuación se muestra la ilustración del enfoque anterior:
CPP
// CPP program to find the largest non perfect
// square number among n numbers
#include <bits/stdc++.h>
using namespace std;
bool check(int n)
{
// takes the sqrt of the number
int d = sqrt(n);
// checks if it is a perfect square number
if (d * d == n)
return true;
return false;
}
// function to find the largest non perfect square number
int largestNonPerfectSquareNumber(int a[], int n)
{
// stores the maximum of all non perfect square numbers
int maxi = -1;
// traverse for all elements in the array
for (int i = 0; i < n; i++) {
// store the maximum if not a perfect square
if (!check(a[i]))
maxi = max(a[i], maxi);
}
return maxi;
}
// driver code to check the above functions
int main()
{
int a[] = { 16, 20, 25, 2, 3, 10 };
int n = sizeof(a) / sizeof(a[0]);
// function call
cout << largestNonPerfectSquareNumber(a, n);
return 0;
}
Java
// Java program to find the
// largest non perfect
// square number among n numbers
import java.io.*;
class GfG{
static Boolean check(int n)
{
// takes the sqrt of the number
int d = (int)Math.sqrt(n);
// checks if it is a perfect square number
if (d * d == n)
return true;
return false;
}
// function to find the largest
// non perfect square number
static int largestNonPerfectSquareNumber(int a[], int n)
{
// stores the maximum of all
// non perfect square numbers
int maxi = -1;
// traverse for all elements in the array
for (int i = 0; i < n; i++) {
// store the maximum if
// not a perfect square
if (!check(a[i]))
maxi = Math.max(a[i], maxi);
}
return maxi;
}
public static void main (String[] args) {
int a[] = { 16, 20, 25, 2, 3, 10 };
int n = a.length;
// function call
System.out.println(largestNonPerfectSquareNumber(a, n));
}
}
// This code is contributed by Gitanjali.
Python3
# python program to find # the largest non perfect # square number among n numbers import math def check( n): # takes the sqrt of the number d = int(math.sqrt(n)) # checks if it is a # perfect square number if (d * d == n): return True return False # function to find the largest # non perfect square number def largestNonPerfectSquareNumber(a, n): # stores the maximum of all # non perfect square numbers maxi = -1 # traverse for all elements # in the array for i in range(0,n): # store the maximum if # not a perfect square if (check(a[i])==False): maxi = max(a[i], maxi) return maxi # driver code a = [ 16, 20, 25, 2, 3, 10 ] n= len(a) # function call print (largestNonPerfectSquareNumber(a, n)) # This code is contributed by Gitanjali.
C#
// C# program to find the largest non perfect
// square number among n numbers
using System;
class GfG {
static bool check(int n)
{
// takes the sqrt of the number
int d = (int)Math.Sqrt(n);
// checks if it is a perfect
// square number
if (d * d == n)
return true;
return false;
}
// function to find the largest
// non perfect square number
static int largestNonPerfectSquareNumber(
int []a, int n)
{
// stores the maximum of all
// non perfect square numbers
int maxi = -1;
// traverse for all elements in
// the array
for (int i = 0; i < n; i++) {
// store the maximum if
// not a perfect square
if (!check(a[i]))
maxi = Math.Max(a[i], maxi);
}
return maxi;
}
// driver code to check the above functions
public static void Main ()
{
int []a = { 16, 20, 25, 2, 3, 10 };
int n = a.Length;
// function call
Console.WriteLine(
largestNonPerfectSquareNumber(a, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find
// the largest non perfect
// square number among n
// numbers
function check($n)
{
// takes the sqrt
// of the number
$d = sqrt($n);
// checks if it is a
// perfect square number
if ($d * $d == $n)
return true;
return false;
}
// function to find the largest
// non perfect square number
function largestNonPerfectSquareNumber($a, $n)
{
// stores the maximum of
// all non perfect square
// numbers
$maxi = -1;
// traverse for all
// elements in the array
for ($i = 0; $i < $n; $i++)
{
// store the maximum if
// not a perfect square
if (!check($a[$i]))
$maxi = max($a[$i], $maxi);
}
return $maxi;
}
// Driver Code
$a = array(16, 20, 25, 2, 3, 10);
$n = count($a);
// function call
echo largestNonPerfectSquareNumber($a, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find the
// largest non perfect
// square number among n numbers
function check(n)
{
// takes the sqrt of the number
let d = Math.sqrt(n);
// checks if it is a perfect square number
if (d * d == n)
return true;
return false;
}
// function to find the largest
// non perfect square number
function largestNonPerfectSquareNumber(a, n)
{
// stores the maximum of all
// non perfect square numbers
let maxi = -1;
// traverse for all elements in the array
for (let i = 0; i < n; i++) {
// store the maximum if
// not a perfect square
if (!check(a[i]))
maxi = Math.max(a[i], maxi);
}
return maxi;
}
// Driver Code
let a = [ 16, 20, 25, 2, 3, 10 ];
let n = a.length;
// function call
document.write(largestNonPerfectSquareNumber(a, n));
</script>
Producción:
20
La complejidad del tiempo se puede considerar como O (n) ya que la función sqrt() se puede implementar en el tiempo O (1) para números enteros de tamaño fijo (32 bits o 64 bits) [Consulte Wiki para obtener más detalles]
?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p