Given an array arr[] and an integer K, the task is to find a subarray of length K having a sum which is a perfect square. If no such subarray exists, then print -1. Otherwise, print the subarray.
Note: There can be more than one possible subarray. Print any one of them.
Examples:
Input: arr[] = {20, 34, 51, 10, 99, 87, 23, 45}, K = 3
Output: {10, 99, 87}
Explanation: The sum of the elements of the subarray {10, 99, 87} is 196, which is a perfect square (162 = 196).Input: arr[] = {20, 34, 51, 10, 99, 87, 23, 45}, K = 4
Output: -1
Explanation: None of the subarrays of size K has a sum which is a perfect square.
Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays of size K and check whether the sum of any subarray generated is a perfect square or not. If found to be true, print that subarray. If no subarray satisfies the condition, print “-1”.
Time Complexity: O(N*K)
Auxiliary Space: O(K)
Efficient Approach: An efficient approach is to use a sliding window technique to find the sum of a contiguous subarray of size K and then check if the sum is a perfect square or not using Binary Search. Below are the steps to solve this problem:
- Compute the sum of the first K array elements and store it in a variable, say curr_sum.
- Then iterate over the remaining array elements one by one, and update curr_sum by adding ith element and removing (i – K)th element from the array.
- For every value of curr_sum obtained, check if it is a perfect square number or not.
- If found to be true for any value of curr_sum, then print the corresponding subarray.
- Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a given number// is a perfect square or notbool isPerfectSquare(int n){ // Find square root of n double sr = sqrt(n); // Check if the square root // is an integer or not return ((sr - floor(sr)) == 0);}// Function to print the subarray// whose sum is a perfect squarevoid SubarrayHavingPerfectSquare( vector<int> arr, int k){ pair<int, int> ans; int sum = 0, i; // Sum of first K elements for (i = 0; i < k; i++) { sum += arr[i]; } bool found = false; // If the first k elements have // a sum as perfect square if (isPerfectSquare(sum)) { ans.first = 0; ans.second = i - 1; } else { // Iterate through the array for (int j = i; j < arr.size(); j++) { sum = sum + arr[j] - arr[j - k]; // If sum is perfect square if (isPerfectSquare(sum)) { found = true; ans.first = j - k + 1; ans.second = j; } } for (int k = ans.first; k <= ans.second; k++) { cout << arr[k] << " "; } } // If subarray not found if (found == false) { cout << "-1"; }}// Driver Codeint main(){ // Given array vector<int> arr; arr = { 20, 34, 51, 10, 99, 87, 23, 45 }; // Given subarray size K int K = 3; // Function Call SubarrayHavingPerfectSquare(arr, K); return 0;} |
Java
// Java program for // the above approachimport java.io.*;public class GFG{ static class pair{ int first, second; }// Function to check if a given number// is a perfect square or notstatic boolean isPerfectSquare(int n){ // Find square root of n double sr = Math.sqrt(n); // Check if the square root // is an integer or not return ((sr - Math.floor(sr)) == 0);}// Function to print the subarray// whose sum is a perfect squarestatic void SubarrayHavingPerfectSquare(int[] arr, int k){ pair ans = new pair(); int sum = 0, i; // Sum of first K elements for (i = 0; i < k; i++) { sum += arr[i]; } boolean found = false; // If the first k elements have // a sum as perfect square if (isPerfectSquare(sum)) { ans.first = 0; ans.second = i - 1; } else { // Iterate through the array for (int j = i; j < arr.length; j++) { sum = sum + arr[j] - arr[j - k]; // If sum is perfect square if (isPerfectSquare(sum)) { found = true; ans.first = j - k + 1; ans.second = j; } } for (int k1 = ans.first; k1 <= ans.second; k1++) { System.out.print(arr[k1] + " "); } } // If subarray not found if (found == false) { System.out.print("-1"); }}// Driver Codepublic static void main(String[] args){ // Given array int []arr = {20, 34, 51, 10, 99, 87, 23, 45}; // Given subarray size K int K = 3; // Function Call SubarrayHavingPerfectSquare(arr, K);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approachfrom math import sqrt, ceil, floor# Function to check if a given number# is a perfect square or notdef isPerfectSquare(n): # Find square root of n sr = sqrt(n) # Check if the square root # is an integer or not return ((sr - floor(sr)) == 0)# Function to print the subarray# whose sum is a perfect squaredef SubarrayHavingPerfectSquare(arr, k): ans = [ 0, 0 ] sum = 0 # Sum of first K elements i = 0 while i < k: sum += arr[i] i += 1 found = False # If the first k elements have # a sum as perfect square if (isPerfectSquare(sum)): ans[0] = 0 ans[1] = i - 1 else: # Iterate through the array for j in range(i, len(arr)): sum = sum + arr[j] - arr[j - k] # If sum is perfect square if (isPerfectSquare(sum)): found = True ans[0] = j - k + 1 ans[1] = j for k in range(ans[0], ans[1] + 1): print(arr[k], end = " ") # If subarray not found if (found == False): print("-1")# Driver Codeif __name__ == '__main__': # Given array arr = [ 20, 34, 51, 10, 99, 87, 23, 45 ] # Given subarray size K K = 3 # Function call SubarrayHavingPerfectSquare(arr, K)# This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;class GFG{ class pair{ public int first, second; } // Function to check if a given number// is a perfect square or notstatic bool isPerfectSquare(int n){ // Find square root of n double sr = Math.Sqrt(n); // Check if the square root // is an integer or not return ((sr - Math.Floor(sr)) == 0);}// Function to print the subarray// whose sum is a perfect squarestatic void SubarrayHavingPerfectSquare(int[] arr, int k){ pair ans = new pair(); int sum = 0, i; // Sum of first K elements for (i = 0; i < k; i++) { sum += arr[i]; } bool found = false; // If the first k elements have // a sum as perfect square if (isPerfectSquare(sum)) { ans.first = 0; ans.second = i - 1; } else { // Iterate through the array for (int j = i; j < arr.Length; j++) { sum = sum + arr[j] - arr[j - k]; // If sum is perfect square if (isPerfectSquare(sum)) { found = true; ans.first = j - k + 1; ans.second = j; } } for (int k1 = ans.first; k1 <= ans.second; k1++) { Console.Write(arr[k1] + " "); } } // If subarray not found if (found == false) { Console.Write("-1"); }}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = {20, 34, 51, 10, 99, 87, 23, 45}; // Given subarray size K int K = 3; // Function Call SubarrayHavingPerfectSquare(arr, K);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Function to check if a given number// is a perfect square or notfunction isPerfectSquare(n){ // Find square root of n var sr = Math.sqrt(n); // Check if the square root // is an integer or not return ((sr - Math.floor(sr)) == 0);}// Function to print the subarray// whose sum is a perfect squarefunction SubarrayHavingPerfectSquare( arr, k){ var ans = []; var sum = 0, i; // Sum of first K elements for (i = 0; i < k; i++) { sum += arr[i]; } var found = false; // If the first k elements have // a sum as perfect square if (isPerfectSquare(sum)) { ans[0] = 0; ans[1] = i - 1; } else { // Iterate through the array for (var j = i; j < arr.length; j++) { sum = sum + arr[j] - arr[j - k]; // If sum is perfect square if (isPerfectSquare(sum)) { found = true; ans[0] = j - k + 1; ans[1] = j; } } for (var k = ans[0]; k <= ans[1]; k++) { document.write( arr[k] + " "); } } // If subarray not found if (found == false) { document.write( "-1"); }}// Driver Code// Given arrayvar arr = [20, 34, 51, 10, 99, 87, 23, 45 ];// Given subarray size Kvar K = 3;// Function CallSubarrayHavingPerfectSquare(arr, K);</script> |
Output
10 99 87
Time Complexity: O(N*log(sum))
Auxiliary Space:O(1)
Approach 2: Dynamic Programming:
To solve this problem using dynamic programming, we can create a 2D array where dp[i][j] represents the sum of the subarray from index i to index j. We can calculate the values of dp[i][j] using the following recurrence relation:
- dp[i][j] = dp[i][j-1] + arr[j]
- Then, we can iterate over all subarrays of size K and check if the sum of the subarray is a perfect square. If we find such a subarray, we can print it and return.
Here’s the codes:
C++
#include <bits/stdc++.h>using namespace std;// Function to check if a given number// is a perfect square or notbool isPerfectSquare(int n){ // Find square root of n int sr = sqrt(n); // Check if the square root // is an integer or not return ((sr * sr) == n);}// Function to print the subarray// whose sum is a perfect squarevoid SubarrayHavingPerfectSquare( vector<int>& arr, int K){ int n = arr.size(); // Create dp array to store sum // of subarrays from index i to j int dp[n][n]; memset(dp, 0, sizeof(dp)); // Fill dp array for (int i = 0; i < n; i++) { dp[i][i] = arr[i]; for (int j = i + 1; j < n; j++) { dp[i][j] = dp[i][j - 1] + arr[j]; } } bool found = false; // Iterate over all subarrays of size K for (int i = 0; i <= n - K; i++) { int sum = dp[i][i + K - 1]; // If sum is a perfect square if (isPerfectSquare(sum)) { found = true; for (int j = i; j < i + K; j++) { cout << arr[j] << " "; } break; } } // If subarray not found if (found == false) { cout << "-1"; }}// Driver Codeint main(){ // Given array vector<int> arr = { 20, 34, 51, 10, 99, 87, 23, 45 }; // Given subarray size K int K = 3; // Function Call SubarrayHavingPerfectSquare(arr, K); return 0;} |
Java
import java.util.*;public class SubarrayHavingPerfectSquare { // Function to check if a given number // is a perfect square or not static boolean isPerfectSquare(int n) { // Find square root of n int sr = (int)Math.sqrt(n); // Check if the square root // is an integer or not return (sr * sr == n); } // Function to print the subarray // whose sum is a perfect square static void subarrayHavingPerfectSquare(List<Integer> arr, int K) { int n = arr.size(); // Create dp array to store sum // of subarrays from index i to j int[][] dp = new int[n][n]; // Fill dp array for (int i = 0; i < n; i++) { dp[i][i] = arr.get(i); for (int j = i + 1; j < n; j++) { dp[i][j] = dp[i][j - 1] + arr.get(j); } } boolean found = false; // Iterate over all subarrays of size K for (int i = 0; i <= n - K; i++) { int sum = dp[i][i + K - 1]; // If sum is a perfect square if (isPerfectSquare(sum)) { found = true; for (int j = i; j < i + K; j++) { System.out.print(arr.get(j) + " "); } break; } } // If subarray not found if (found == false) { System.out.print("-1"); } } // Driver Code public static void main(String[] args) { // Given array List<Integer> arr = Arrays.asList(20, 34, 51, 10, 99, 87, 23, 45); // Given subarray size K int K = 3; // Function Call subarrayHavingPerfectSquare(arr, K); }} |
Python3
# Python3 program for the above approachimport math# Function to check if a given number# is a perfect square or notdef isPerfectSquare(n): # Find square root of n sr = int(math.sqrt(n)) # Check if the square root # is an integer or not return sr * sr == n# Function to print the subarray# whose sum is a perfect squaredef SubarrayHavingPerfectSquare(arr, K): n = len(arr) # Create dp array to store sum # of subarrays from index i to j dp = [[0] * n for _ in range(n)] # Fill dp array for i in range(n): dp[i][i] = arr[i] for j in range(i + 1, n): dp[i][j] = dp[i][j - 1] + arr[j] found = False # Iterate over all subarrays of size K for i in range(n - K + 1): sum = dp[i][i + K - 1] # If sum is a perfect square if isPerfectSquare(sum): found = True for j in range(i, i + K): print(arr[j], end=" ") break # If subarray not found if not found: print("-1")# Driver Codeif __name__ == "__main__": # Given array arr = [20, 34, 51, 10, 99, 87, 23, 45] # Given subarray size K K = 3 # Function Call SubarrayHavingPerfectSquare(arr, K)# This code is contributed by Utkarsh Kumar |
C#
// C# code addition using System;using System.Collections.Generic;public class GFG{ // Function to check if a given number // is a perfect square or not static bool IsPerfectSquare(int n) { // Find square root of n int sr = (int)Math.Sqrt(n); // Check if the square root // is an integer or not return (sr * sr == n); } // Function to print the subarray // whose sum is a perfect square static void SubarrayHavingPerfectSquare(List<int> arr, int K) { int n = arr.Count; // Create dp array to store sum // of subarrays from index i to j int[,] dp = new int[n, n]; // Fill dp array for (int i = 0; i < n; i++) { dp[i, i] = arr[i]; for (int j = i + 1; j < n; j++) { dp[i, j] = dp[i, j - 1] + arr[j]; } } bool found = false; // Iterate over all subarrays of size K for (int i = 0; i <= n - K; i++) { int sum = dp[i, i + K - 1]; // If sum is a perfect square if (IsPerfectSquare(sum)) { found = true; for (int j = i; j < i + K; j++) { Console.Write(arr[j] + " "); } break; } } // If subarray not found if (!found) { Console.Write("-1"); } } // Driver Code public static void Main(string[] args) { // Given array List<int> arr = new List<int> { 20, 34, 51, 10, 99, 87, 23, 45 }; // Given subarray size K int K = 3; // Function Call SubarrayHavingPerfectSquare(arr, K); }}// The code is contributed by Arushi Goel. |
Javascript
// Javascript program for the above approach// Function to check if a given number// is a perfect square or notfunction isPerfectSquare(n) { // Find square root of n let sr = Math.floor(Math.sqrt(n)); // Check if the square root // is an integer or not return sr * sr === n;}// Function to print the subarray// whose sum is a perfect squarefunction subarrayHavingPerfectSquare(arr, K) { let n = arr.length; // Create dp array to store sum // of subarrays from index i to j let dp = new Array(n).fill(0).map(() => new Array(n).fill(0)); // Fill dp array for (let i = 0; i < n; i++) { dp[i][i] = arr[i]; for (let j = i + 1; j < n; j++) { dp[i][j] = dp[i][j - 1] + arr[j]; } } let found = false; // Iterate over all subarrays of size K for (let i = 0; i <= n - K; i++) { let sum = dp[i][i + K - 1]; // If sum is a perfect square if (isPerfectSquare(sum)) { found = true; for (let j = i; j < i + K; j++) { console.log(arr[j]); } break; } } // If subarray not found if (!found) { console.log("-1"); }}// Driver Code// Given arraylet arr = [20, 34, 51, 10, 99, 87, 23, 45];// Given subarray size Klet K = 3;// Function CallsubarrayHavingPerfectSquare(arr, K); |
Output:
10 99 87
Time Complexity: O(n * sqrt(n)), where n is the size of the input array.
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!
