Given an array arr[] of size N and an integer S, the task is to find the count of quadruplets present in the given array having sum S.
Examples:
Input: arr[] = {1, 5, 3, 1, 2, 10}, S = 20
Output: 1
Explanation: Only quadruplet satisfying the conditions is arr[1] + arr[2] + arr[4] + arr[5] = 5 + 3 + 2 + 10 = 20.Input: N = 6, S = 13, arr[] = {4, 5, 3, 1, 2, 4}
Output: 3
Explanation: Three quadruplets with sum 13 are:
- arr[0] + arr[2] + arr[4] + arr[5] = 4 + 3 + 2 + 4 = 13
- arr[0] + arr[1] + arr[2] + arr[3] = 4 + 5 + 3 + 1 = 13
- arr[1] + arr[2] + arr[3] + arr[5] = 5 + 3 + 1 + 4 = 13
Naive Approach: The idea is to generate all possible combinations of length 4 from the given array. For each quadruplet, if the sum equals S, then increment the counter by 1. After checking all the quadruplets, print the counter as the total number of quadruplets having sum S.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to return the number of // quadruplets with the given sum int countSum( int a[], int n, int sum) { // Initialize variables int i, j, k, l; // Initialize answer int count = 0; // All possible first elements for (i = 0; i < n - 3; i++) { // All possible second elements for (j = i + 1; j < n - 2; j++) { // All possible third elements for (k = j + 1; k < n - 1; k++) { // All possible fourth elements for (l = k + 1; l < n; l++) { // Increment counter by 1 // if quadruplet sum is S if (a[i] + a[j] + a[k] + a[l] == sum) count++; } } } } // Return the final count return count; } // Driver Code int main() { // Given array arr[] int arr[] = { 4, 5, 3, 1, 2, 4 }; // Given sum S int S = 13; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << countSum(arr, N, S); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to return the number of // quadruplets with the given sum static int countSum( int a[], int n, int sum) { // Initialize variables int i, j, k, l; // Initialize answer int count = 0 ; // All possible first elements for (i = 0 ; i < n - 3 ; i++) { // All possible second elements for (j = i + 1 ; j < n - 2 ; j++) { // All possible third elements for (k = j + 1 ; k < n - 1 ; k++) { // All possible fourth elements for (l = k + 1 ; l < n; l++) { // Increment counter by 1 // if quadruplet sum is S if (a[i] + a[j] + a[k] + a[l] == sum) count++; } } } } // Return the final count return count; } // Driver Code public static void main(String args[]) { // Given array arr[] int arr[] = { 4 , 5 , 3 , 1 , 2 , 4 }; // Given sum S int S = 13 ; int N = arr.length; // Function Call System.out.print(countSum(arr, N, S)); } } // This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approach # Function to return the number of # quadruplets with the given sum def countSum(a, n, sum ): # Initialize variables # i, j, k, l # Initialize answer count = 0 # All possible first elements for i in range (n - 3 ): # All possible second elements for j in range (i + 1 , n - 2 ): # All possible third elements for k in range (j + 1 , n - 1 ): # All possible fourth elements for l in range (k + 1 , n): # Increment counter by 1 # if quadruplet sum is S if (a[i] + a[j] + a[k] + a[l] = = sum ): count + = 1 # Return the final count return count # Driver Code if __name__ = = '__main__' : # Given array arr[] arr = [ 4 , 5 , 3 , 1 , 2 , 4 ] # Given sum S S = 13 N = len (arr) # Function Call print (countSum(arr, N, S)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach class GFG{ // Function to return the number of // quadruplets with the given sum static int countSum( int []a, int n, int sum) { // Initialize variables int i, j, k, l; // Initialize answer int count = 0; // All possible first elements for (i = 0; i < n - 3; i++) { // All possible second elements for (j = i + 1; j < n - 2; j++) { // All possible third elements for (k = j + 1; k < n - 1; k++) { // All possible fourth elements for (l = k + 1; l < n; l++) { // Increment counter by 1 // if quadruplet sum is S if (a[i] + a[j] + a[k] + a[l] == sum) count++; } } } } // Return the final count return count; } // Driver Code public static void Main() { // Given array arr[] int []arr = { 4, 5, 3, 1, 2, 4 }; // Given sum S int S = 13; int N = arr.Length; // Function Call System.Console.Write(countSum(arr, N, S)); } } // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // Javascript program to implement // the above approach // Function to return the number of // quadruplets with the given sum function countSum(a, n, sum) { // Initialize variables let i, j, k, l; // Initialize answer let count = 0; // All possible first elements for (i = 0; i < n - 3; i++) { // All possible second elements for (j = i + 1; j < n - 2; j++) { // All possible third elements for (k = j + 1; k < n - 1; k++) { // All possible fourth elements for (l = k + 1; l < n; l++) { // Increment counter by 1 // if quadruplet sum is S if (a[i] + a[j] + a[k] + a[l] == sum) count++; } } } } // Return the final count return count; } // Driver Code // Given array arr[] let arr = [ 4, 5, 3, 1, 2, 4 ]; // Given sum S let S = 13; let N = arr.length; // Function Call document.write(countSum(arr, N, S)); </script> |
Output:
3
Time Complexity: O(N4)
Auxiliary Space: O(1)
Better Approach: To optimize the above approach, the idea is to use a Map data structure. Follow the steps below to solve the problem:
- Initialize the counter count with 0 to store the number of quadruplets.
- Traverse the given array over the range [0, N – 3)using the variable i. For each element arr[i], traverse the array again over the range [i + 1, N – 2) using the variable j and do the following:
- Find the value of the required sum(say req) as (S – arr[i] – arr[j]).
- Initialize the count_twice with 0 that will store the count of ordered pairs in the above subarray with sum (S – arr[i] – arr[j]).
- After finding the count_twice, update the count by count_twice / 2.
- After the above steps, print the value of count as the result.
Below is the implementation of the above idea:
C++
// C++ program for the above approach #include <iostream> #include <unordered_map> using namespace std; // Function to return the number of // quadruplets having given sum int countSum( int a[], int n, int sum) { // Initialize variables int i, j, k, l; // Initialize answer int count = 0; // All possible first elements for (i = 0; i < n - 3; i++) { // All possible second element for (j = i + 1; j < n - 2; j++) { int req = sum - a[i] - a[j]; // Use map to find the // fourth element unordered_map< int , int > m; // All possible third elements for (k = j + 1; k < n; k++) m[a[k]]++; int twice_count = 0; // Calculate number of valid // 4th elements for (k = j + 1; k < n; k++) { // Update the twice_count twice_count += m[req - a[k]]; if (req - a[k] == a[k]) twice_count--; } // Unordered pairs count += twice_count / 2; } } // Return answer return count; } // Driver Code int main() { // Given array arr[] int arr[] = { 4, 5, 3, 1, 2, 4 }; // Given sum S int S = 13; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << countSum(arr, N, S); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to return the number of // quadruplets having given sum static int countSum( int a[], int n, int sum) { // Initialize variables int i, j, k, l; // Initialize answer int count = 0 ; // All possible first elements for (i = 0 ; i < n - 3 ; i++) { // All possible second element for (j = i + 1 ; j < n - 2 ; j++) { int req = sum - a[i] - a[j]; // Use map to find the // fourth element HashMap<Integer, Integer> m = new HashMap<>(); // All possible third elements for (k = j + 1 ; k < n; k++) if (m.containsKey(a[k])) { m.put(a[k], m.get(a[k]) + 1 ); } else { m.put(a[k], 1 ); } int twice_count = 0 ; // Calculate number of valid // 4th elements for (k = j + 1 ; k < n; k++) { // Update the twice_count if (m.containsKey(req - a[k])) twice_count += m.get(req - a[k]); if (req - a[k] == a[k]) twice_count--; } // Unordered pairs count += twice_count / 2 ; } } // Return answer return count; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 4 , 5 , 3 , 1 , 2 , 4 }; // Given sum S int S = 13 ; int N = arr.length; // Function Call System.out.print(countSum(arr, N, S)); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach # Function to return the number of # quadruplets having given sum def countSum(a, n, sum ): # Initialize variables # Initialize answer count = 0 # All possible first elements for i in range (n - 3 ): # All possible second element for j in range (i + 1 , n - 2 , 1 ): req = sum - a[i] - a[j] # Use map to find the # fourth element m = {} # All possible third elements for k in range (j + 1 , n, 1 ): m[a[k]] = m.get(a[k], 0 ) + 1 twice_count = 0 # Calculate number of valid # 4th elements for k in range (j + 1 , n, 1 ): # Update the twice_count twice_count + = m.get(req - a[k], 0 ) if (req - a[k] = = a[k]): twice_count - = 1 # Unordered pairs count + = twice_count / / 2 # Return answer return count # Driver Code if __name__ = = '__main__' : # Given array arr[] arr = [ 4 , 5 , 3 , 1 , 2 , 4 ] # Given sum S S = 13 N = len (arr) # Function Call print (countSum(arr, N, S)) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to return the number of // quadruplets having given sum static int countSum( int []a, int n, int sum) { // Initialize variables int i, j, k; //int l; // Initialize answer int count = 0; // All possible first elements for (i = 0; i < n - 3; i++) { // All possible second element for (j = i + 1; j < n - 2; j++) { int req = sum - a[i] - a[j]; // Use map to find the // fourth element Dictionary< int , int > m = new Dictionary< int , int >(); // All possible third elements for (k = j + 1; k < n; k++) if (m.ContainsKey(a[k])) { m[a[k]]++; } else { m.Add(a[k], 1); } int twice_count = 0; // Calculate number of valid // 4th elements for (k = j + 1; k < n; k++) { // Update the twice_count if (m.ContainsKey(req - a[k])) twice_count += m[req - a[k]]; if (req - a[k] == a[k]) twice_count--; } // Unordered pairs count += twice_count / 2; } } // Return answer return count; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = { 4, 5, 3, 1, 2, 4 }; // Given sum S int S = 13; int N = arr.Length; // Function Call Console.Write(countSum(arr, N, S)); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program for the above approach // Function to return the number of // quadruplets having given sum function countSum(a, n, sum) { // Initialize variables var i, j, k, l; // Initialize answer var count = 0; // All possible first elements for (i = 0; i < n - 3; i++) { // All possible second element for (j = i + 1; j < n - 2; j++) { var req = sum - a[i] - a[j]; // Use map to find the // fourth element var m = new Map(); // All possible third elements for (k = j + 1; k < n; k++) { if (m.has(a[k])) m.set(a[k], m.get(a[k])+1) else m.set(a[k], 1) } var twice_count = 0; // Calculate number of valid // 4th elements for (k = j + 1; k < n; k++) { // Update the twice_count if (m.has(req - a[k])) twice_count += m.get(req - a[k]); if ((req - a[k]) == a[k]) twice_count--; } // Unordered pairs count += parseInt(twice_count / 2); } } // Return answer return count; } // Driver Code // Given array arr[] var arr = [4, 5, 3, 1, 2, 4]; // Given sum S var S = 13; var N = arr.length; // Function Call document.write( countSum(arr, N, S)); </script> |
Output:
3
Time complexity: O(N3) where N is the size of the given array,
Auxiliary Space: O(N)
Efficient Approach: The idea is similar to the above approach using a map. In this approach, fix the 3rd element, then find and store the frequency of sums of all possible first two elements of any quadruplet of the given array. Follow the below steps to solve the problem:
- Initialize the counter count to store the total quadruplets with the given sum S and a map to store all possible sums for the first two elements of each possible quadruplet.
- Traverse the given array over the range [0, N – 1] using the variable i where arr[i] is the fixed 3rd element.
- Then for each element arr[i] in the above step, traverse the given array over the range [i + 1, N – 1] using the variable j and increment the counter count by map[arr[i] + arr[j]].
- After traversing from the above loop, for each element arr[i], traverse the array arr[] from j = 0 to i – 1 and increment the frequency of any sum arr[i] + arr[j] of the first two elements of any possible quadruplet by 1 i.e., increment map[arr[i] + arr[j]] by 1.
- Repeat the above steps for each element arr[i] and then print the counter count as the total number of quadruplets with the given sum S.
Below is the implementation of the above idea:
C++
// C++ program for the above approach #include <iostream> #include <unordered_map> using namespace std; // Function to return the number of // quadruplets having the given sum int countSum( int a[], int n, int sum) { // Initialize variables int i, j, k; // Initialize answer int count = 0; // Store the frequency of sum // of first two elements unordered_map< int , int > m; // Traverse from 0 to N-1, where // arr[i] is the 3rd element for (i = 0; i < n - 1; i++) { // All possible 4th elements for (j = i + 1; j < n; j++) { // Sum of last two element int temp = a[i] + a[j]; // Frequency of sum of first // two elements if (temp < sum) count += m[sum - temp]; } for (j = 0; j < i; j++) { // Store frequency of all possible // sums of first two elements int temp = a[i] + a[j]; if (temp < sum) m[temp]++; } } // Return the answer return count; } // Driver Code int main() { // Given array arr[] int arr[] = { 4, 5, 3, 1, 2, 4 }; // Given sum S int S = 13; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << countSum(arr, N, S); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to return the number of // quadruplets having the given sum static int countSum( int a[], int n, int sum) { // Initialize variables int i, j, k; // Initialize answer int count = 0 ; // Store the frequency of sum // of first two elements HashMap<Integer, Integer> m = new HashMap<>(); // Traverse from 0 to N-1, where // arr[i] is the 3rd element for (i = 0 ; i < n - 1 ; i++) { // All possible 4th elements for (j = i + 1 ; j < n; j++) { // Sum of last two element int temp = a[i] + a[j]; // Frequency of sum of first // two elements if (temp < sum && m.containsKey(sum - temp)) count += m.get(sum - temp); } for (j = 0 ; j < i; j++) { // Store frequency of all possible // sums of first two elements int temp = a[i] + a[j]; if (temp < sum) if (m.containsKey(temp)) m.put(temp, m.get(temp) + 1 ); else m.put(temp, 1 ); } } // Return the answer return count; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 4 , 5 , 3 , 1 , 2 , 4 }; // Given sum S int S = 13 ; int N = arr.length; // Function Call System.out.print(countSum(arr, N, S)); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach from collections import defaultdict # Function to return the number of # quadruplets having the given sum def countSum(a, n, sum ): # Initialize answer count = 0 # Store the frequency of sum # of first two elements m = defaultdict( int ) # Traverse from 0 to N-1, where # arr[i] is the 3rd element for i in range (n - 1 ): # All possible 4th elements for j in range (i + 1 , n): # Sum of last two element temp = a[i] + a[j] # Frequency of sum of first # two elements if (temp < sum ): count + = m[ sum - temp] for j in range (i): # Store frequency of all possible # sums of first two elements temp = a[i] + a[j] if (temp < sum ): m[temp] + = 1 # Return the answer return count # Driver Code if __name__ = = "__main__" : # Given array arr[] arr = [ 4 , 5 , 3 , 1 , 2 , 4 ] # Given sum S S = 13 N = len (arr) # Function Call print (countSum(arr, N, S)) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to return the number of // quadruplets having the given sum static int countSum( int []a, int n, int sum) { // Initialize variables int i, j; // Initialize answer int count = 0; // Store the frequency of sum // of first two elements Dictionary< int , int > m = new Dictionary< int , int >(); // Traverse from 0 to N-1, where // arr[i] is the 3rd element for (i = 0; i < n - 1; i++) { // All possible 4th elements for (j = i + 1; j < n; j++) { // Sum of last two element int temp = a[i] + a[j]; // Frequency of sum of first // two elements if (temp < sum && m.ContainsKey(sum - temp)) count += m[sum - temp]; } for (j = 0; j < i; j++) { // Store frequency of all possible // sums of first two elements int temp = a[i] + a[j]; if (temp < sum) if (m.ContainsKey(temp)) m[temp]++; else m.Add(temp, 1); } } // Return the answer return count; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = { 4, 5, 3, 1, 2, 4 }; // Given sum S int S = 13; int N = arr.Length; // Function Call Console.Write(countSum(arr, N, S)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach // Function to return the number of // quadruplets having the given sum function countSum(a, n, sum) { // Initialize variables let i, j, k; // Initialize answer let count = 0; // Store the frequency of sum // of first two elements let m = new Map(); // Traverse from 0 to N-1, where // arr[i] is the 3rd element for (i = 0; i < n - 1; i++) { // All possible 4th elements for (j = i + 1; j < n; j++) { // Sum of last two element let temp = a[i] + a[j]; // Frequency of sum of first // two elements if (temp < sum && m.has(sum - temp)) count += m.get(sum - temp); } for (j = 0; j < i; j++) { // Store frequency of all possible // sums of first two elements let temp = a[i] + a[j]; if (temp < sum) if (m.has(temp)) m.set(temp, m.get(temp) + 1); else m.set(temp, 1); } } // Return the answer return count; } // Driver Code // Given array arr[] let arr = [ 4, 5, 3, 1, 2, 4 ]; // Given sum S let S = 13; let N = arr.length; // Function Call document.write(countSum(arr, N, S)); // This code is contributed by avanitrachhadiya2155 </script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!