Largest sub-array whose all elements are perfect squares

0 0 4 minutes read

Given an array $arr$ of integer elements, the task is to find the length of the largest sub-array of $arr$ such that all the elements of the sub-array are perfect squares.

Examples:

Input: arr[] = {1, 7, 36, 4, 49, 2, 4}
Output: 3
Maximum length sub-array with all elements as perfect squares is {36, 4, 49}

Input: arr[] = {25, 100, 2, 3, 9, 1}
Output: 2
Possible sub-array is {25, 100}

Approach:

Traverse the array from left to right. Initialize a max_length and current_length variable with 0.
Take an integer and a float variable and for every element of the array store it’s square root in both these variables.
If both the variables are equal i.e. the current element is a perfect square then increment current_length variable and continue. Otherwise, set current_length = 0.
At each step, assign max_length as max_length = max(current_length, max_length).
Print the value of max_length in the end.

Below is the implementation of the above approach:

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>

Output

Complexity Analysis:

Time Complexity: O(nlogn)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!