Count quadruples from four sorted arrays whose sum is equal to a given value x
Last Updated :
27 Sep, 2022
Given four sorted arrays each of size n of distinct elements. Given a value x. The problem is to count all quadruples(group of four numbers) from all the four arrays whose sum is equal to x.
Note: The quadruple has an element from each of the four arrays.
Examples:
Input : arr1 = {1, 4, 5, 6},
arr2 = {2, 3, 7, 8},
arr3 = {1, 4, 6, 10},
arr4 = {2, 4, 7, 8}
n = 4, x = 30
Output : 4
The quadruples are:
(4, 8, 10, 8), (5, 7, 10, 8),
(5, 8, 10, 7), (6, 7, 10, 7)
Input : For the same above given fours arrays
x = 25
Output : 14
Method 1 (Naive Approach):
Using four nested loops generate all quadruples and check whether elements in the quadruple sum up to x or not.
C++
#include <bits/stdc++.h>
using namespace std;
int countQuadruples(int arr1[], int arr2[],
int arr3[], int arr4[], int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
if ((arr1[i] + arr2[j] + arr3[k] + arr4[l]) == x)
count++;
return count;
}
int main()
{
int arr1[] = { 1, 4, 5, 6 };
int arr2[] = { 2, 3, 7, 8 };
int arr3[] = { 1, 4, 6, 10 };
int arr4[] = { 2, 4, 7, 8 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int x = 30;
cout << "Count = "
<< countQuadruples(arr1, arr2, arr3,
arr4, n, x);
return 0;
}
|
Java
class GFG {
static int countQuadruples(int arr1[], int arr2[],
int arr3[], int arr4[], int n, int x) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
for (int l = 0; l < n; l++)
{
if ((arr1[i] + arr2[j] + arr3[k] + arr4[l]) == x) {
count++;
}
}
}
}
}
return count;
}
public static void main(String[] args) {
int arr1[] = {1, 4, 5, 6};
int arr2[] = {2, 3, 7, 8};
int arr3[] = {1, 4, 6, 10};
int arr4[] = {2, 4, 7, 8};
int n = arr1.length;
int x = 30;
System.out.println("Count = "
+ countQuadruples(arr1, arr2, arr3,
arr4, n, x));
}
}
|
Python3
def countquadruples(arr1, arr2,
arr3, arr4, n, x):
count = 0
for i in range(n):
for j in range(n):
for k in range(n):
for l in range(n):
if (arr1[i] + arr2[j] +
arr3[k] + arr4[l] == x):
count += 1
return count
arr1 = [1, 4, 5, 6]
arr2 = [2, 3, 7, 8]
arr3 = [1, 4, 6, 10]
arr4 = [2, 4, 7, 8 ]
n = len(arr1)
x = 30
print("Count = ", countquadruples(arr1, arr2,
arr3, arr4, n, x))
|
C#
using System;
public class GFG {
static int countQuadruples(int []arr1, int []arr2,
int []arr3, int []arr4, int n, int x) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
for (int l = 0; l < n; l++)
{
if ((arr1[i] + arr2[j] + arr3[k] + arr4[l]) == x) {
count++;
}
}
}
}
}
return count;
}
public static void Main() {
int []arr1 = {1, 4, 5, 6};
int []arr2 = {2, 3, 7, 8};
int []arr3 = {1, 4, 6, 10};
int []arr4 = {2, 4, 7, 8};
int n = arr1.Length;
int x = 30;
Console.Write("Count = "
+ countQuadruples(arr1, arr2, arr3,
arr4, n, x));
}
}
|
PHP
<?php
function countQuadruples(&$arr1, &$arr2,
&$arr3, &$arr4,
$n, $x)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
for ($k = 0; $k < $n; $k++)
for ($l = 0; $l < $n; $l++)
if (($arr1[$i] + $arr2[$j] +
$arr3[$k] + $arr4[$l]) == $x)
$count++;
return $count;
}
$arr1 = array( 1, 4, 5, 6 );
$arr2 = array( 2, 3, 7, 8 );
$arr3 = array( 1, 4, 6, 10 );
$arr4 = array( 2, 4, 7, 8 );
$n = sizeof($arr1);
$x = 30;
echo "Count = " . countQuadruples($arr1, $arr2, $arr3,
$arr4, $n, $x);
?>
|
Javascript
<script>
function countQuadruples(arr1,arr2,arr3,arr4,n,x)
{
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
for (let l = 0; l < n; l++)
{
if ((arr1[i] + arr2[j] + arr3[k] + arr4[l]) == x) {
count++;
}
}
}
}
}
return count;
}
let arr1=[1, 4, 5, 6];
let arr2=[2, 3, 7, 8];
let arr3=[1, 4, 6, 10];
let arr4=[2, 4, 7, 8];
let n = arr1.length;
let x = 30;
document.write("Count = "
+ countQuadruples(arr1, arr2, arr3,
arr4, n, x));
</script>
|
Output:
Count = 4
Time Complexity: O(n4)
Auxiliary Space: O(1)
Method 2 (Binary Search): Generate all triplets from the 1st three arrays. For each triplet so generated, find the sum of elements in the triplet. Let it be T. Now, search the value (x – T) in the 4th array. If the value found in the 4th array, then increment count. This process is repeated for all the triplets generated from the 1st three arrays.
C++
#include <bits/stdc++.h>
using namespace std;
bool isPresent(int arr[], int low, int high, int value)
{
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return false;
}
int countQuadruples(int arr1[], int arr2[], int arr3[],
int arr4[], int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++) {
int T = arr1[i] + arr2[j] + arr3[k];
if (isPresent(arr4, 0, n, x - T))
count++;
}
return count;
}
int main()
{
int arr1[] = { 1, 4, 5, 6 };
int arr2[] = { 2, 3, 7, 8 };
int arr3[] = { 1, 4, 6, 10 };
int arr4[] = { 2, 4, 7, 8 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int x = 30;
cout << "Count = "
<< countQuadruples(arr1, arr2, arr3, arr4, n, x);
return 0;
}
|
Java
class GFG
{
static boolean isPresent(int[] arr, int low,
int high, int value)
{
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return false;
}
static int countQuadruples(int[] arr1, int[] arr2,
int[] arr3, int[] arr4,
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
{
int T = arr1[i] + arr2[j] + arr3[k];
if (isPresent(arr4, 0, n-1, x - T))
count++;
}
return count;
}
public static void main(String[] args)
{
int[] arr1 = { 1, 4, 5, 6 };
int[] arr2 = { 2, 3, 7, 8 };
int[] arr3 = { 1, 4, 6, 10 };
int[] arr4 = { 2, 4, 7, 8 };
int n = 4;
int x = 30;
System.out.println( "Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
}
}
|
Python3
def isPresent(arr,low,high,value):
while(low<=high):
mid=(low+high)//2
if(arr[mid]==value):
return True
elif(arr[mid]>value):
high=mid-1
else:
low=mid+1
return False
def countQuadruples(arr1,arr2,arr3,arr4,n,x):
count=0
for i in range(n):
for j in range(n):
for k in range(n):
T=arr1[i]+arr2[j]+arr3[k]
if(isPresent(arr4,0,n-1,x-T)):
count=count+1
return count
arr1=[1, 4, 5, 6]
arr2=[2, 3, 7, 8]
arr3=[1, 4, 6, 10]
arr4=[2, 4, 7, 8]
n=len(arr1)
x=30
print("Count = {}".format(countQuadruples(arr1,arr2,arr3,arr4,n,x)))
|
C#
using System;
class GFG
{
static bool isPresent(int[] arr, int low,
int high, int value)
{
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return false;
}
static int countQuadruples(int[] arr1, int[] arr2,
int[] arr3, int[] arr4,
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
{
int T = arr1[i] + arr2[j] + arr3[k];
if (isPresent(arr4, 0, n-1, x - T))
count++;
}
return count;
}
public static void Main(String[] args)
{
int[] arr1 = { 1, 4, 5, 6 };
int[] arr2 = { 2, 3, 7, 8 };
int[] arr3 = { 1, 4, 6, 10 };
int[] arr4 = { 2, 4, 7, 8 };
int n = 4;
int x = 30;
Console.WriteLine( "Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
}
}
|
PHP
<?php
function isPresent($arr, $low, $high, $value)
{
while ($low <= $high)
{
$mid = ($low + $high) / 2;
if ($arr[$mid] == $value)
return true;
else if ($arr[$mid] > $value)
$high = $mid - 1;
else
$low = $mid + 1;
}
return false;
}
function countQuadruples($arr1, $arr2, $arr3,
$arr4, $n, $x)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
for ($k = 0; $k < $n; $k++)
{
$T = $arr1[$i] + $arr2[$j] + $arr3[$k];
if (isPresent($arr4, 0, $n, $x - $T))
$count++;
}
return $count;
}
$arr1 = array(1, 4, 5, 6);
$arr2 = array(2, 3, 7, 8);
$arr3 = array(1, 4, 6, 10);
$arr4 = array(2, 4, 7, 8);
$n = sizeof($arr1);
$x = 30;
echo "Count = " . countQuadruples($arr1, $arr2, $arr3,
$arr4, $n, $x);
?>
|
Javascript
<script>
function isPresent(arr, low, high, value)
{
while (low <= high)
{
let mid = parseInt((low + high) / 2, 10);
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return false;
}
function countQuadruples(arr1, arr2, arr3, arr4, n, x)
{
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
for (let k = 0; k < n; k++)
{
let T = arr1[i] + arr2[j] + arr3[k];
if (isPresent(arr4, 0, n-1, x - T))
count++;
}
return count;
}
let arr1 = [ 1, 4, 5, 6 ];
let arr2 = [ 2, 3, 7, 8 ];
let arr3 = [ 1, 4, 6, 10 ];
let arr4 = [ 2, 4, 7, 8 ];
let n = 4;
let x = 30;
document.write( "Count = " + countQuadruples(arr1, arr2, arr3, arr4, n, x));
</script>
|
Output:
Count = 4
Time Complexity: O(n3logn)
Auxiliary Space: O(1)
Method 3 (Use of two pointers): Generate all pairs from the 1st two arrays. For each pair so generated, find the sum of elements in the pair. Let it be p_sum. For each p_sum, count pairs from the 3rd and 4th sorted array with sum equal to (x – p_sum). Accumulate these count in the total_count of quadruples.
C++
#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr1[], int arr2[], int n, int value)
{
int count = 0;
int l = 0, r = n - 1;
while (l < n & amp; &r >= 0) {
int sum = arr1[l] + arr2[r];
if (sum == value) {
l++, r--;
count++;
}
else if (sum > value)
r--;
else
l++;
}
return count;
}
int countQuadruples(int arr1[], int arr2[], int arr3[],
int arr4[], int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int p_sum = arr1[i] + arr2[j];
count += countPairs(arr3, arr4, n, x - p_sum);
}
return count;
}
int main()
{
int arr1[] = { 1, 4, 5, 6 };
int arr2[] = { 2, 3, 7, 8 };
int arr3[] = { 1, 4, 6, 10 };
int arr4[] = { 2, 4, 7, 8 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int x = 30;
cout << "Count = "
<< countQuadruples(arr1, arr2, arr3,
arr4, n, x);
return 0;
}
|
Java
class GFG {
static int countPairs(int arr1[], int arr2[], int n, int value)
{
int count = 0;
int l = 0, r = n - 1;
while (l < n & r >= 0) {
int sum = arr1[l] + arr2[r];
if (sum == value) {
l++; r--;
count++;
}
else if (sum > value)
r--;
else
l++;
}
return count;
}
static int countQuadruples(int arr1[], int arr2[], int arr3[],
int arr4[], int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int p_sum = arr1[i] + arr2[j];
count += countPairs(arr3, arr4, n, x - p_sum);
}
return count;
}
static public void main(String[] args) {
int arr1[] = {1, 4, 5, 6};
int arr2[] = {2, 3, 7, 8};
int arr3[] = {1, 4, 6, 10};
int arr4[] = {2, 4, 7, 8};
int n = arr1.length;
int x = 30;
System.out.println("Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
}
}
|
Python3
def countPairs(arr1, arr2,
n, value):
count = 0
l = 0
r = n - 1
while (l < n and r >= 0):
sum = arr1[l] + arr2[r]
if (sum == value):
l += 1
r -= 1
count += 1
elif (sum > value):
r -= 1
else:
l += 1
return count
def countQuadruples(arr1, arr2,
arr3, arr4,
n, x):
count = 0
for i in range(0, n):
for j in range(0, n):
p_sum = arr1[i] + arr2[j]
count += int(countPairs(arr3, arr4,
n, x - p_sum))
return count
arr1 = [1, 4, 5, 6]
arr2 = [2, 3, 7, 8]
arr3 = [1, 4, 6, 10]
arr4 = [2, 4, 7, 8]
n = len(arr1)
x = 30
print("Count = ", countQuadruples(arr1, arr2,
arr3, arr4,
n, x))
|
C#
using System;
public class GFG {
static int countPairs(int []arr1, int []arr2, int n, int value)
{
int count = 0;
int l = 0, r = n - 1;
while (l < n & r >= 0) {
int sum = arr1[l] + arr2[r];
if (sum == value) {
l++; r--;
count++;
}
else if (sum > value)
r--;
else
l++;
}
return count;
}
static int countQuadruples(int []arr1, int []arr2, int []arr3,
int []arr4, int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int p_sum = arr1[i] + arr2[j];
count += countPairs(arr3, arr4, n, x - p_sum);
}
return count;
}
static public void Main() {
int []arr1 = {1, 4, 5, 6};
int []arr2 = {2, 3, 7, 8};
int []arr3 = {1, 4, 6, 10};
int []arr4 = {2, 4, 7, 8};
int n = arr1.Length;
int x = 30;
Console.Write("Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
}
}
|
Javascript
<script>
function countPairs(arr1,arr2,n,value)
{
let count = 0;
let l = 0, r = n - 1;
while (l < n & r >= 0) {
let sum = arr1[l] + arr2[r];
if (sum == value) {
l++; r--;
count++;
}
else if (sum > value)
r--;
else
l++;
}
return count;
}
function countQuadruples(arr1,arr2,arr3,arr4,n,x)
{
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) {
let p_sum = arr1[i] + arr2[j];
count += countPairs(arr3, arr4, n, x - p_sum);
}
return count;
}
let arr1=[1, 4, 5, 6];
let arr2=[2, 3, 7, 8];
let arr3=[1, 4, 6, 10];
let arr4=[2, 4, 7, 8];
let n = arr1.length;
let x = 30;
document.write("Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
</script>
|
Output:
Count = 4
Time Complexity: O(n3)
Auxiliary Space: O(1)
Method 4 Efficient Approach(Hashing): Create a hash table where (key, value) tuples are represented as (sum, frequency) tuples. Here the sum are obtained from the pairs of 1st and 2nd array and their frequency count is maintained in the hash table. Hash table is implemented using unordered_map in C++. Now, generate all pairs from the 3rd and 4th array. For each pair so generated, find the sum of elements in the pair. Let it be p_sum. For each p_sum, check whether (x – p_sum) exists in the hash table or not. If it exists, then add the frequency of (x – p_sum) to the count of quadruples.
C++
#include <bits/stdc++.h>
using namespace std;
int countQuadruples(int arr1[], int arr2[], int arr3[],
int arr4[], int n, int x)
{
int count = 0;
unordered_map<int, int> um;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
um[arr1[i] + arr2[j]]++;
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++) {
int p_sum = arr3[k] + arr4[l];
if (um.find(x - p_sum) != um.end())
count += um[x - p_sum];
}
return count;
}
int main()
{
int arr1[] = { 1, 4, 5, 6 };
int arr2[] = { 2, 3, 7, 8 };
int arr3[] = { 1, 4, 6, 10 };
int arr4[] = { 2, 4, 7, 8 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int x = 30;
cout << "Count = "
<< countQuadruples(arr1, arr2, arr3, arr4, n, x);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int countQuadruples(int arr1[], int arr2[], int arr3[],
int arr4[], int n, int x)
{
int count = 0;
Map<Integer,Integer> m = new HashMap<>();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if(m.containsKey(arr1[i] + arr2[j]))
m.put((arr1[i] + arr2[j]), m.get((arr1[i] + arr2[j]))+1);
else
m.put((arr1[i] + arr2[j]), 1);
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
{
int p_sum = arr3[k] + arr4[l];
if (m.containsKey(x - p_sum))
count += m.get(x - p_sum);
}
return count;
}
public static void main(String[] args)
{
int arr1[] = { 1, 4, 5, 6 };
int arr2[] = { 2, 3, 7, 8 };
int arr3[] = { 1, 4, 6, 10 };
int arr4[] = { 2, 4, 7, 8 };
int n = arr1.length;
int x = 30;
System.out.println("Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
}
}
|
Python3
def countQuadruples(arr1, arr2, arr3, arr4, n, x):
count = 0
m = {}
for i in range(n):
for j in range(n):
if (arr1[i] + arr2[j]) in m:
m[arr1[i] + arr2[j]] += 1
else:
m[arr1[i] + arr2[j]] = 1
for k in range(n):
for l in range(n):
p_sum = arr3[k] + arr4[l]
if (x - p_sum) in m:
count += m[x - p_sum]
return count
arr1 = [1, 4, 5, 6]
arr2 = [2, 3, 7, 8 ]
arr3 = [1, 4, 6, 10]
arr4 = [2, 4, 7, 8 ]
n = len(arr1)
x = 30
print("Count =", countQuadruples(arr1, arr2, arr3, arr4, n, x))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static int countQuadruples(int []arr1, int []arr2, int []arr3,
int []arr4, int n, int x)
{
int count = 0;
Dictionary<int,int> m = new Dictionary<int,int>();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if(m.ContainsKey(arr1[i] + arr2[j])){
var val = m[arr1[i] + arr2[j]];
m.Remove(arr1[i] + arr2[j]);
m.Add((arr1[i] + arr2[j]), val+1);
}
else
m.Add((arr1[i] + arr2[j]), 1);
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
{
int p_sum = arr3[k] + arr4[l];
if (m.ContainsKey(x - p_sum))
count += m[x - p_sum];
}
return count;
}
public static void Main(String[] args)
{
int []arr1 = { 1, 4, 5, 6 };
int []arr2 = { 2, 3, 7, 8 };
int []arr3 = { 1, 4, 6, 10 };
int []arr4 = { 2, 4, 7, 8 };
int n = arr1.Length;
int x = 30;
Console.WriteLine("Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
}
}
|
Javascript
<script>
function countQuadruples(arr1,arr2,arr3,arr4,n,X)
{
let count = 0;
let m = new Map();
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if(m.has(arr1[i] + arr2[j]))
m.set((arr1[i] + arr2[j]), m.get((arr1[i] + arr2[j]))+1);
else
m.set((arr1[i] + arr2[j]), 1);
for (let k = 0; k < n; k++)
for (let l = 0; l < n; l++)
{
let p_sum = arr3[k] + arr4[l];
if (m.has(x - p_sum))
count += m.get(x - p_sum);
}
return count;
}
let arr1 = [ 1, 4, 5, 6 ];
let arr2 = [ 2, 3, 7, 8 ];
let arr3 = [ 1, 4, 6, 10 ];
let arr4 = [ 2, 4, 7, 8 ];
let n = arr1.length;
let x = 30;
document.write("Count = "
+ countQuadruples(arr1, arr2, arr3, arr4, n, x));
</script>
|
Output:
Count = 4
Time Complexity: O(n2)
Auxiliary Space: O(n2)
count pairs in the 3rd and 4th sorted array with sum equal to (x – p_sum)
Please Login to comment...