Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Example of Counting Quadruples
3.
Algorithm (Naive Approach)
4.
Naive Approach Explanation
5.
Code in C++ (Naive Approach)
6.
Code in Java (Naive Approach)
7.
Code in Python (Naive Approach)
8.
Complexities (Naive Approach)
9.
Algorithm (Hashing Method)
10.
Hashing Approach Explanation
11.
Code in C++ (Hashing Method)
12.
Code in Java (Hashing Method)
13.
Code in Python (Hashing Method)
14.
Complexities (Hashing Method)
15.
Frequently Asked Questions
15.1.
What is Hashing?
15.2.
What is Hash Function?
15.3.
What is a Hash Table?
15.4.
What is a Map?
15.5.
What is the difference between Map and Hash Table?
16.
Conclusion
Last Updated: Mar 27, 2024
Easy

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

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Quadruples is the group of four numbers, counting Quadruples from sorted arrays whose sum equals a given value x.

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

It is a process in which we try to discover quadruples using different arrays in such a way that the sum of elements of all quadruples will be the same and equal to the given value x. It is a hashing problem.

Example of Counting Quadruples

Now, Let's understand the concept clearly using the example:

Let's suppose that there are four sorted arrays named array1[], array2[], array3[], and array4[], each of size L of unique elements. It's also given a value of x. Now the question is to find all the quadruples from all the four sorted arrays whose sum is x. 

Input:

array1 = { 1, 3, 4, 7 }
array2 = { 2, 5, 6, 8 }
array3 = { 1, 2, 5, 8 }
array4 = { 3, 4, 7, 9 }

L = 4 and x = 30

 

Output:

Number of Quadruples = 2
{ 7, 6, 8, 9 }, { 7, 8, 8, 9 }
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Count quadruples from four sorted arrays whose sum is equal to a given value x (naive approach)

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.

Count quadruples from four sorted arrays whose sum is equal to a given value x (naive approach)

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.

Count quadruples from four sorted arrays whose sum is equal to a given value x (naive approach)

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;
}

 

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));
	}
}

 

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))

 

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.

Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)

var total

Step 2:

Now we declare a map sum-frequency

Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)

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:

Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)

Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)
Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)

Step 4:

Repeat step 3 for successive two arrays.

Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)

Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)
Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)

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
Count quadruples from four sorted arrays whose sum is equal to a given value x (Hashing approach)

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;
}

 

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));
     }
 }

 

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))

 

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,

 

Recommended problems -

 

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!

Previous article
Count pairs with given sum
Next article
Count pairs whose products exist in array
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass