Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

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.

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.

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.

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

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.

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

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.

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

Set total = 0.

Declare a map.

Traverse the first and second array and store the sum of each pair with the two lists into the map together with their frequency.

Repeat step 3 for the other two arrays.

Choose a sum of each pair from the two arrays and check whether the x-sum is present in a map.

If available, then obtain their frequency and add it to the value of total.

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

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.