Count quadruples from four sorted arrays whose sum is equal to a given value x

Algorithm (Naive Approach)

Here is an algorithm to Count Quadruples from four sorted arrays whose sum is equal to a given value x.

1. Given 4 arrays of length s. Declare four nested loops: loop 1 (loop counter i), loop 2 (loop counter j), loop3 (loop counter k), loop4 (loop counter l). All four loops have n iterations ( from 0 to s).
    
2. The counter of these four for loops represents the index of 4 elements of the quadruple. Get the sum of ith, jth, kth and lth elements and compare it with x.
    
3. If it is equal, print the quadruple array, and repeat step 4 for other results.

Naive Approach Explanation

Step 1:

Since we have given 4 arrays so in order to iterate all the arrays we will declare 4 loops, one for each array in a nested manner.

Counters of the loops will represent the index of the arrays.

Step 2:

Now we will iterate the loops and find the sum of all the elements of the quadruple formed by the iteration of the nested loop. We will compare whether the sum of Elements of the quadruples is equal to x or not.

Step 3:

Now If the sum of all the elements will be equal to the value of x then we will print that quadruple and repeat the previous process to find all the quadruples having sum==x.

Code in C++ (Naive Approach)

C++ program to Count Quadruples from four sorted arrays whose sum is equal to a given value x.

#include <bits/stdc++.h>
using namespace std;

int TotalQuadruple(int array1[], int array2[],
int array3[], int array4[], int s, int x)
{
	int total = 0;

	/* generate all possible quadruples from the four sorted arrays */
	
	for (int i = 0; i < s; i++)
		for (int j = 0; j < s; j++)
			for (int k = 0; k < s; k++)
				for (int l = 0; l < s; l++)
					/* check whether elements of quadruple sum up to x or not */
					if ((array1[i] + array2[j] + array3[k] + array4[l]) == x)
						total++;

	/* required count of quadruples */
	return total;
}


// Driver program to test above
int main()
{
	/* four sorted arrays each of size 'n' */
	int array1[]={1, 3, 4, 7};
	int array2[]={2, 5, 6, 8};
	int array3[]={1, 2, 5, 8};
	int array4[]={3, 4, 7, 9};

	int s = sizeof(array1) / sizeof(array1[0]);
	int x = 30;
	cout << "Total = " << TotalQuadruple(array1, array2, array3, array4, s, x);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

OUTPUT

Code in Java (Naive Approach)

Java program to Count Quadruples from four sorted arrays whose sum is equal to a given value x.

class CN {
	static int TotalQuadruple(int array1[], int array2[], int array3[], int array4[], int s, int x) {
		int total = 0;

		/* generate all possible quadruples from the four sorted arrays */
		
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				for (int k = 0; k < s; k++) {
					for (int l = 0; l < s; l++) {
						/* check whether elements of quadruple sum up to x or not */
						if ((array1[i] + array2[j] + array3[k] + array4[l]) == x) {
							total++;
						}
					}
				}
			}
		}

		/* required count of quadruples */
		return total;
	}

	// Driver program to test above
	public static void main(String[] args) {

		/* four sorted arrays each of size 'n' */
		int array1[]={1, 3, 4, 7};
		int array2[]={2, 5, 6, 8};
		int array3[]={1, 2, 5, 8};
		int array4[]={3, 4, 7, 9};

		int s = array1.length;
		int x = 30;
		System.out.println("Total = " + TotalQuadruple(array1, array2, array3, array4, s, x));
	}
}

You can also try this code with Online Java Compiler

Run Code

OUTPUT

Code in Python (Naive Approach)

Python program to Count Quadruples from four sorted arrays whose sum is equal to a given value x.

def TotalQuuadruple(array1, array2, array3, array4, s, x):
	total = 0

	# generate all possible quadruples from the four sorted arrays
	for i in range(s):
		for j in range(s):
			for k in range(s):
				for l in range(s):
					# check whether elements of quadruple sum up to x or not
					if (array1[i] + array2[j] + array3[k] + array4[l] == x):
						total += 1
	
	# required count of quadruples
	return total


array1=[1, 3, 4, 7]
array2=[2, 5, 6, 8]
array3=[1, 2, 5, 8]
array4=[3, 4, 7, 9]

s = len(array1)
x = 30
print("Total = ", TotalQuuadruple(array1, array2, array3, array4, s, x))

You can also try this code with Online Python Compiler

Run Code

OUTPUT

Complexities (Naive Approach)

Time Complexity

The Time Complexity of the Naive approach to solve the ““Count quadruples from four sorted arrays whose sum is equal to a given value x” problem is: "O(n4)", where n is the number of elements of an array.

Space Complexity

The space Complexity of the Naive approach to solve the ““Count quadruples from four sorted arrays whose sum is equal to a given value x” problem is: "O(1)". It means we do not use any extra space.

You can also read about the Longest Consecutive Sequence.

Algorithm (Hashing Method)

Here is an Algorithm to Count Quadruples from four sorted arrays whose sum is equal to a given value x.

1. Set total = 0.
    
2. Declare a map.
    
3. Traverse the first and second array and store the sum of each pair with the two lists into the map together with their frequency.
    
4. Repeat step 3 for the other two arrays.
    
5. Choose a sum of each pair from the two arrays and check whether the x-sum is present in a map.
    
6. If available, then obtain their frequency and add it to the value of total.
    
7. Return total.

Hashing Approach Explanation

Step 1:

We will declare a var total and assign its value to 0. This variable will hold the number of quadruples.

var total

Step 2:

Now we declare a map sum-frequency

Step 3:

Now this time, we will iterate the first two arrays and store the sum of pairs made by iteration of two arrays and their frequencies in the map as key and value.

Like:

Step 4:

Repeat step 3 for successive two arrays.

Step 5:

Now we will check whether x-sum1 is available in sum2

x-(7,6): sum = 13: 30-13 = 17 (Available in sum2)
x-(7,8): sum = 15: 30-15 = 15 (Available in sum2)

Step 6:

If available, It means we found the quadruple, then we obtain their frequency and add it to the total value.

x-(7,6): sum = 13  30-13 = 17  (Available in sum 2)  Frequency = 1
x-(7,8): sum = 15  30-15 = 15  (Available in sum 2)  Frequency = 1

var total

Check out this problem - Pair Sum In Array.

Code in C++ (Hashing Method)

Given below is the C++ program to count quadruples from four sorted arrays whose sum is equal to a given value x using hashing technique.

#include <iostream> 
#include<unordered_map> 
using namespace std;

int getNumberOfQuadruples(int array1[], int array2[], int array3[],int array4[], int s, int x) 
{
	int total = 0;
	unordered_map<int, int> MAP;
	for (int i = 0; i < s; i++)
		for (int j = 0; j < s; j++)
			MAP [array1[i] + array2[j]]++;
	
	for (int k = 0; k < s; k++)
		for (int l = 0; l < s; l++)
		{
			int a_sum = array3[k] + array4[l];
			if (MAP.find(x - a_sum) != MAP.end())
				total += MAP [x - a_sum];
		}
		
	return total;
}

int main()
{ 
	int array1[]={1, 3, 4, 7};
	int array2[]={2, 5, 6, 8};
	int array3[]={1, 2, 5, 8};
	int array4[]={3, 4, 7, 9};
	int s = sizeof(array1) / sizeof(array1[0]);
	int x = 30;
	
	cout << "total = "<< getNumberOfQuadruples (array1, array2, array3, array4, s, x);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

OUTPUT

Code in Java (Hashing Method)

Given below is the Java Program to count quadruples from four sorted arrays whose sum is equal to a given value x using hashing technique.

import java.util.HashMap;
class QuadrupletsSum
{
	public static int getNumberOfQuadruples (int array1[], int array2[], int array3[], int array4[], int s, int x)
	{
		int total = 0;
		HashMap<Integer,Integer> MAP = new HashMap<>();
		for (int i = 0; i < s; i++)
			for (int j = 0; j < s; j++)
				if(MAP.containsKey(array1[i] + array2[j]))
					MAP.put((array1[i] + array2[j]), MAP.get((array1[i] + array2[j]))+1);
				else
					MAP.put((array1[i] + array2[j]), 1);
					
		for (int k = 0; k < s; k++)
			for (int l = 0; l < s; l++)
			{
				int a_sum = array3[k] + array4[l];
				if (MAP.containsKey(x - a_sum))
					total += MAP.get(x - a_sum);
			}
			
		return total;
	}

	public static void main(String[] args)
	{
		int array1[]={1, 3, 4, 7};
		int array2[]={2, 5, 6, 8};
		int array3[]={1, 2, 5, 8};
		int array4[]={3, 4, 7, 9};

		int s = array1.length;
		int x = 30;
		System.out.println("Total = " + getNumberOfQuadruples (array1, array2, array3, array4, s, x));
     }
 }

You can also try this code with Online Java Compiler

Run Code

OUTPUT

Code in Python (Hashing Method)

Given below is the Python Program to Count Quadruples from Four Sorted Arrays Whose Sum is Equal to a Given Value x.

def totalQuad(array1, array2, array3, array4, s, x):
	total = 0
	d = {}
	for i in range(s):
		for j in range(s):
			if (array1[i] + array2[j]) in d:
				d[array1[i] + array2[j]] += 1
			else:
				d[array1[i] + array2[j]] = 1
					
	for k in range(s):
    	for l in range(s):
    		a_sum = array3[k] + array4[l]
    		if (x - a_sum) in d:
        		total += d[x - a_sum]
        		
	return total
 
array1 = [1, 3, 4, 7]
array2 = [2, 5, 6, 8]
array3 = [1, 2, 5, 8]
array4 = [3, 4, 7, 9]

s = len(array1)
x = 30
print("Total =", totalQuad(array1, array2, array3, array4, s, x))

You can also try this code with Online Python Compiler

Run Code

OUTPUT

Complexities (Hashing Method)

Time Complexity

The Time Complexity of the Hashing method to solve the “Count quadruples from four sorted arrays whose sum is equal to a given value x” problem is: "O(n2)", where n is the number of elements of an array.

Space Complexity

The space Complexity of the above Hashing method to solve the ““Count quadruples from four sorted arrays whose sum is equal to a given value x” problem is: "O(n2)", where n is the number of elements of an array.

Frequently Asked Questions

What is Hashing?

The process of mapping keys into the Hash Table with the help of the Hash function is known as Hashing.

What is Hash Function?

Hash Function is a function that maps the data of random size to fixed values. The values returned by the Hash function are known as hash values, hash codes, or hashes.

What is a Hash Table?

Hash Table is a container that stores information in two parts, i.e., key and value. For indexing and storing data in the Hash Table, there requires a Hash Function.

What is a Map?

A map is a container that stores a key-pair value. Each element consists of a key and its value.

What is the difference between Map and Hash Table?

They both use hashing techniques to store key-value pairs, but the difference between them is that Map allows storing a single null key and multiple null values, whereas Hashtable doesn't allow any null key and null value.

Conclusion

In this blog, we learned how to solve Count Quadruples from four sorted arrays whose sum is equal to a given value x is a problem using Hashing technique. We understood the problem statement with the help of examples and also learned about algorithms to solve the problem, and we implemented the algorithm using different programming languages.

Also read,

• Find all pairs (a,b) in an array such that a%b=k
• Count Divisible Pairs in an Array 
• Minimum number of Subsets with Distinct Elements

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our guided paths on Coding Ninjas Studio to learn more about C programming, DSA, JavaScript, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!