Given an array 
of integer elements, the task is to find the length of the largest sub-array of 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 squareint 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 codeint 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 squareimport 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 squarefrom math import sqrt# function to return the length of the# largest sub-array of an array every# element of whose is a perfect squaredef 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 codeif __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 squareusing System;class GFG { // function to return the length of the// largest sub-array of an array every// element of whose is a perfect squarestatic 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 squarefunction 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 squarefunction 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 codevar arr = [9, 75, 4, 64, 121, 25 ];var n = arr.length;document.write( contiguousPerfectSquare(arr, n));</script> |
Output
4
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
