Given an array arr[], the task is to find the sum of a subsequence that forms a perfect square. If there are multiple subsequences having a sum equal to a perfect square, print the maximum sum.
Explanation:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Output: 36
Explanation:
Maximum possible sum which is a perfect square that can be obtained from the array is 36 obtained from the subsequence {1, 5, 6, 7, 8, 9}.
Input: arr[] = {9, 10}
Output: 9
Naive Approach: Generate all the possible subsequences of a given array and for each subsequence, check if its sum is a Perfect Square. If such a sum is found, update the maximum sum. Finally, print the maximum sum obtained.
Time Complexity: O(N * 2N)
Auxiliary Space: O(N)
Efficient Approach:
The above approach can be optimized by using Dynamic Programming approach.
Follow the steps given below:
- Calculate the sum of the array.
- Iterate k in the range [?sum, 0] and check if any subsequence exists with that sum k2. For every k, follow the steps below:
- Initialize boolean matrix subset[][] of dimensions N * sum, where sum denotes the current value of k2.
- subset[i][j] denotes whether a subsequence of size i with sum j exists or not.
- Initialize first column and first row as true and false respectively of subset[][].
- Run two nested loops, outer from i in the range [1, N] and inner j in the range [1, sum]to fill the subset[][] matrix in bottom up manner based on the following conditions:
- if (j < arr[i – 1]), then subset[i][j] = subset[i – 1][j]
- if (j >= arr[i – 1]), then subset[i][j] = subset[i – 1][j] || subset[i – 1][j – arr[i – 1]]
- Finally, return the subset[n][sum].
- The first k for which subset[n][k] is true, gives the required maximum possible subsequence sum k2.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;bool isSubsetSum(int arr[], int n, int sum){ bool subset[n + 1][sum + 1]; // If sum is 0, then answer is true for (int i = 0; i <= n; i++) subset[i][0] = true; // If sum is not 0 and arr[] is empty, // then answer is false for (int i = 1; i <= sum; i++) subset[0][i] = false; // Fill the subset table in bottom up manner for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { if (j < arr[i - 1]) subset[i][j] = subset[i - 1][j]; if (j >= arr[i - 1]) subset[i][j] = subset[i - 1][j] || subset[i - 1][j - arr[i - 1]]; } } return subset[n][sum];}// Function to find the sumint findSum(int* arr, int n){ int sum = 0; // Find sum of all values for (int i = 0; i < n; i++) { sum += arr[i]; } int val = sqrt(sum); for (int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findSum(arr, n) << endl; return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{static boolean isSubsetSum(int arr[], int n, int sum){ boolean[][] subset = new boolean[n + 1][sum + 1]; // If sum is 0, then answer is true for(int i = 0; i <= n; i++) subset[i][0] = true; // If sum is not 0 and arr[] is empty, // then answer is false for(int i = 1; i <= sum; i++) subset[0][i] = false; // Fill the subset table in bottom up manner for(int i = 1; i <= n; i++) { for(int j = 1; j <= sum; j++) { if (j < arr[i - 1]) subset[i][j] = subset[i - 1][j]; if (j >= arr[i - 1]) subset[i][j] = subset[i - 1][j] || subset[i - 1][j - arr[i - 1]]; } } return subset[n][sum];}// Function to find the sumstatic int findSum(int[] arr, int n){ int sum = 0; // Find sum of all values for(int i = 0; i < n; i++) { sum += arr[i]; } int val = (int)Math.sqrt(sum); for(int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0;}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = arr.length; System.out.println(findSum(arr, n));}}// This code is contributed by offbeat |
Python3
# Python3 program to implement# the above approachimport mathdef isSubsetSum(arr, n, sum): subset = [ [ True for x in range(sum + 1) ] for y in range(n + 1) ] # If sum is 0, then answer is true for i in range(n + 1): subset[i][0] = True # If sum is not 0 and arr[] is empty, # then answer is false for i in range(1, sum + 1): subset[0][i] = False # Fill the subset table in bottom up manner for i in range(1, n + 1): for j in range(1, sum + 1): if (j < arr[i - 1]): subset[i][j] = subset[i - 1][j] if (j >= arr[i - 1]): subset[i][j] = (subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]) return subset[n][sum]# Function to find the sumdef findSum(arr, n): sum = 0 # Find sum of all values for i in range(n): sum += arr[i] val = int(math.sqrt(sum)) for i in range(val, -1, -1): if (isSubsetSum(arr, n, i * i)): # Return the value; return i * i return 0# Driver Codeif __name__ == "__main__": arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9] n = len(arr) print(findSum(arr, n))# This code is contributed by chitranayal |
C#
// C# program to implement // the above approach using System;class GFG{static bool isSubsetSum(int []arr, int n, int sum){ bool[,] subset = new bool[n + 1, sum + 1]; // If sum is 0, then answer is true for(int i = 0; i <= n; i++) subset[i, 0] = true; // If sum is not 0 and []arr is empty, // then answer is false for(int i = 1; i <= sum; i++) subset[0, i] = false; // Fill the subset table in bottom up manner for(int i = 1; i <= n; i++) { for(int j = 1; j <= sum; j++) { if (j < arr[i - 1]) subset[i, j] = subset[i - 1, j]; if (j >= arr[i - 1]) subset[i, j] = subset[i - 1, j] || subset[i - 1, j - arr[i - 1]]; } } return subset[n, sum];}// Function to find the sumstatic int findSum(int[] arr, int n){ int sum = 0; // Find sum of all values for(int i = 0; i < n; i++) { sum += arr[i]; } int val = (int)Math.Sqrt(sum); for(int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0;}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = arr.Length; Console.WriteLine(findSum(arr, n));}}// This code is contributed by Rohit_ranjan |
Javascript
<script>// JavaScript program to implement// the above approachfunction isSubsetSum(arr, n, sum){ let subset = new Array(n + 1); for (var i = 0; i < subset.length; i++) { subset[i] = new Array(2); } // If sum is 0, then answer is true for(let i = 0; i <= n; i++) subset[i][0] = true; // If sum is not 0 and arr[] is empty, // then answer is false for(let i = 1; i <= sum; i++) subset[0][i] = false; // Fill the subset table in bottom up manner for(let i = 1; i <= n; i++) { for(let j = 1; j <= sum; j++) { if (j < arr[i - 1]) subset[i][j] = subset[i - 1][j]; if (j >= arr[i - 1]) subset[i][j] = subset[i - 1][j] || subset[i - 1][j - arr[i - 1]]; } } return subset[n][sum];} // Function to find the sumfunction findSum(arr, n){ let sum = 0; // Find sum of all values for(let i = 0; i < n; i++) { sum += arr[i]; } let val = Math.floor(Math.sqrt(sum)); for(let i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0;} // Driver Code let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]; let n = arr.length; document.write(findSum(arr, n));</script> |
Output:
36
Time Complexity: O(N * SUM)
Auxiliary Space: O(N * SUM)
Efficient approach : Space optimization
In previous approach the current value subset[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D array subset of size sum+1 and initialize it with false.
- Set a base case and initialize subset[0] = True.
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- At last return the final answer stored in subset[sum].
Implementation:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;bool isSubsetSum(int arr[], int n, int sum){ bool subset[sum + 1]; memset(subset, false, sizeof(subset)); // If sum is 0, then answer is true subset[0] = true; // iterative over subproblems to get the // current value from previous computations for (int i = 0; i < n; i++) { for (int j = sum; j >= arr[i]; j--) { subset[j] = subset[j] || subset[j - arr[i]]; } } // return final answer return subset[sum];}// Function to find the sumint findSum(int* arr, int n){ int sum = 0; // Find sum of all values for (int i = 0; i < n; i++) { sum += arr[i]; } int val = sqrt(sum); for (int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); // function call cout << findSum(arr, n) << endl; return 0;}// this code is contributed by bhardwajji |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG { static boolean isSubsetSum(int[] arr, int n, int sum){ boolean[] subset = new boolean[sum + 1]; Arrays.fill(subset, false); // If sum is 0, then answer is true subset[0] = true; // iterative over subproblems to get the // current value from previous computations for (int i = 0; i < n; i++) { for (int j = sum; j >= arr[i]; j--) { subset[j] = subset[j] || subset[j - arr[i]]; } } // return final answer return subset[sum];}// Function to find the sumstatic int findSum(int[] arr, int n){ int sum = 0; // Find sum of all values for (int i = 0; i < n; i++) { sum += arr[i]; } int val = (int) Math.sqrt(sum); for (int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0;}// Driver Codepublic static void main(String[] args){ int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = arr.length; // function call System.out.println(findSum(arr, n));}} |
Python3
import math# Function to check if a subset with# given sum exists in the arraydef isSubsetSum(arr, n, target): # Initialize a boolean array # subset of size target+1 and # fill it with False subset = [False] * (target + 1) # Set subset[0] to True as a subset # with sum 0 always exists subset[0] = True # Iterate through all elements # in the array for i in range(n): # Iterate backwards through the # subset array starting from target # and going down to arr[i] # This is done to avoid recomputing # subsets that have already been checked for j in range(target, arr[i] - 1, -1): # If subset[j-arr[i]] is True, then # a subset with sum j-arr[i] exists # Therefore, a subset with sum j can # be formed by adding arr[i] to this subset subset[j] = subset[j] or subset[j - arr[i]] # Return True if a subset with the # target sum exists, else False return subset[target]# Function to find the largest perfect square# less than or equal to the sum of all elements# in the arraydef findSum(arr, n): # Find the sum of all elements # in the array total_sum = sum(arr) # Find the square root of the sum of all # elements and cast it to an integer val = int(math.sqrt(total_sum)) # Iterate backwards from the square # root of the sum of all elements for i in range(val, -1, -1): # If a subset with sum i*i exists, # return i*i if isSubsetSum(arr, n, i * i): return i * i # If no perfect square is found, # return 0 return 0# Driver Codeif __name__ == "__main__": # Initialize an array of integers arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] # Find the length of the array n = len(arr) # Call the findSum function and # print the result print(findSum(arr, n)) |
C#
using System;public class GFG { static bool isSubsetSum(int[] arr, int n, int sum) { bool[] subset = new bool[sum + 1]; Array.Fill(subset, false); // If sum is 0, then answer is true subset[0] = true; // iterative over subproblems to get the // current value from previous computations for (int i = 0; i < n; i++) { for (int j = sum; j >= arr[i]; j--) { subset[j] = subset[j] || subset[j - arr[i]]; } } // return final answer return subset[sum]; } static int findSum(int[] arr, int n) { int sum = 0; // Find sum of all values for (int i = 0; i < n; i++) { sum += arr[i]; } int val = (int)Math.Sqrt(sum); for (int i = val; i >= 0; i--) { if (isSubsetSum(arr, n, i * i)) { // return the value; return i * i; } } return 0; } public static void Main() { int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = arr.Length; // function call Console.WriteLine(findSum(arr, n)); }} |
Output
36
Time Complexity: O(N * SUM)
Auxiliary Space: O(SUM)
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!
