Dado un arreglo 
de elementos enteros, la tarea es encontrar la longitud del subarreglo más grande de tal manera que todos los elementos del subarreglo sean cuadrados perfectos.
Ejemplos:
Entrada: arr[] = {1, 7, 36, 4, 49, 2, 4}
Salida: 3
La subarray de longitud máxima con todos los elementos como cuadrados perfectos es {36, 4, 49}
Entrada: arr[] = { 25, 100, 2, 3, 9, 1}
Salida: 2
El subconjunto posible es {25, 100}
Acercarse:
- Atraviesa la array de izquierda a derecha. Inicialice una variable max_length y current_length con 0 .
- Tome un número entero y una variable flotante y para cada elemento de la array almacene su raíz cuadrada en ambas variables.
- Si ambas variables son iguales, es decir, el elemento actual es un cuadrado perfecto, incremente la variable longitud_actual y continúe. De lo contrario, establezca current_length = 0 .
- En cada paso, asigne max_length como max_length = max(current_length, max_length) .
- Imprime el valor de max_length al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect square
#include <bits/stdc++.h>
using namespace std;
// function to return the length of the
// largest sub-array of an array every
// element of whose is a perfect square
int contiguousPerfectSquare(int arr[], int n)
{
int a;
float b;
int current_length = 0;
int max_length = 0;
for (int i = 0; i < n; i++) {
b = sqrt(arr[i]);
a = b;
// if both a and b are equal then
// arr[i] is a perfect square
if (a == b)
current_length++;
else
current_length = 0;
max_length = max(max_length, current_length);
}
return max_length;
}
// Driver code
int main()
{
int arr[] = { 9, 75, 4, 64, 121, 25 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << contiguousPerfectSquare(arr, n);
return 0;
}
Java
// Java program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect square
import java.io.*;
class GFG {
// function to return the length of the
// largest sub-array of an array every
// element of whose is a perfect square
static int contiguousPerfectSquare(int []arr, int n)
{
int a;
float b;
int current_length = 0;
int max_length = 0;
for (int i = 0; i < n; i++) {
b = (float)Math.sqrt(arr[i]);
a = (int)b;
// if both a and b are equal then
// arr[i] is a perfect square
if (a == b)
current_length++;
else
current_length = 0;
max_length = Math.max(max_length, current_length);
}
return max_length;
}
// Driver code
public static void main (String[] args) {
int arr[] = { 9, 75, 4, 64, 121, 25 };
int n = arr.length;
System.out.print(contiguousPerfectSquare(arr, n));
}
}
// This code is contributed by inder_verma..
Python3
# Python 3 program to find the length of # the largest sub-array of an array every # element of whose is a perfect square from math import sqrt # function to return the length of the # largest sub-array of an array every # element of whose is a perfect square def contiguousPerfectSquare(arr, n): current_length = 0 max_length = 0 for i in range(0, n, 1): b = sqrt(arr[i]) a = int(b) # if both a and b are equal then # arr[i] is a perfect square if (a == b): current_length += 1 else: current_length = 0 max_length = max(max_length, current_length) return max_length # Driver code if __name__ == '__main__': arr = [9, 75, 4, 64, 121, 25] n = len(arr) print(contiguousPerfectSquare(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect square
using System;
class GFG {
// function to return the length of the
// largest sub-array of an array every
// element of whose is a perfect square
static int contiguousPerfectSquare(int []arr, int n)
{
int a;
float b;
int current_length = 0;
int max_length = 0;
for (int i = 0; i < n; i++) {
b = (float)Math.Sqrt(arr[i]);
a = (int)b;
// if both a and b are equal then
// arr[i] is a perfect square
if (a == b)
current_length++;
else
current_length = 0;
max_length = Math.Max(max_length, current_length);
}
return max_length;
}
// Driver code
public static void Main () {
int []arr = { 9, 75, 4, 64, 121, 25 };
int n = arr.Length;
Console.WriteLine(contiguousPerfectSquare(arr, n));
}
}
// This code is contributed by inder_verma..
PHP
<?php
// PHP program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect square
// function to return the length of the
// largest sub-array of an array every
// element of whose is a perfect square
function contiguousPerfectSquare($arr, $n)
{
$current_length = 0;
$max_length = 0;
for ($i = 0; $i < $n; $i++)
{
$b = (float)sqrt($arr[$i]);
$a = (int)$b;
// if both a and b are equal then
// arr[i] is a perfect square
if ($a == $b)
$current_length = $current_length + 1;
else
$current_length = 0;
$max_length = max($max_length,
$current_length);
}
return $max_length;
}
// Driver code
$arr = array(9, 75, 4, 64, 121, 25);
$n = sizeof($arr);
echo contiguousPerfectSquare($arr, $n);
// This code os contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect square
// function to return the length of the
// largest sub-array of an array every
// element of whose is a perfect square
function contiguousPerfectSquare(arr, n)
{
var a;
var b;
var current_length = 0;
var max_length = 0;
for (var i = 0; i < n; i++) {
b = (Math.sqrt(arr[i]));
a = parseInt(b);
// if both a and b are equal then
// arr[i] is a perfect square
if (a == b)
current_length++;
else
current_length = 0;
max_length = Math.max(max_length, current_length);
}
return max_length;
}
// Driver code
var arr = [9, 75, 4, 64, 121, 25 ];
var n = arr.length;
document.write( contiguousPerfectSquare(arr, n));
</script>
Producción:
4
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA