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

Difficulty Level Medium
Frequently asked in Accolite Fanatics Moonfrog Labs Synopsys
Array Binary Search Hash Searching SortingViews 1388

Problem Statement

Problem “Count quadruples from four sorted arrays whose sum is equal to a given value x” state that you are given four integer arrays and a value called x. The problem statement asks to find out how many quadruplets can be formed of which sum of elements of each quadruplet can have an addition equal to the given value called x.

Example

int arr1[] = { 2, 5, 6, 9 };

int arr2[] = { 1, 3, 7, 11 };

int arr3[] = { 1, 5, 6, 8 };

int arr4[] = { 2, 3, 5, 10 };

Sum=32
5

Explanation: There are 5 quadruplets which can sum up to give the required value x = 5.

 

Algorithm to count quadruples from four sorted arrays whose sum is  x

1. Set the value of count to 0.
2. Declare a map.
3. Traverse the first and second list and store the sum of each pair that can be formed with the two lists into the map along with their frequency.
4, Traverse the other two arrays.
    1. Pick a sum of each pair from the two arrays and check if the x-sum is present in a map.
        1. If present then gets their frequency and add it to the value of count.
5. Return count.

Explanation

We have given four arrays of integers and a number x. Our task is to find the total number of quadruplets that can be formed which is equal to the x. For that, we are going to use hashing. We will be using a map for that, in this way it will provide an efficient approach to solve this question.

Set the value of count to 0, this count variable is going to store the number of quadruplets. We will declare a map. Start traversing the first two arrays and store the sum of each pair of first two arrays into the map as a key and put the frequency of each sum as a value of key into the map. If we find another pair of a similar value of the sum. We just increase the value of the sum’s frequency. After the complete traversal of the first two arrays, we have a sum of pairs from the first two arrays.

Now we will go for another two arrays traversal, we will pick up the sum of two elements of each pair from an array. One number from one array and one number from another. Then we will check if the difference of x and the sum of this pair is present in a map. Then we will get the frequency of that pair from the map. If present we will be increasing the value of count by adding that frequency to the count, which means we have found one quadruplet from all the arrays. This is because if we have 10+20 =30, then we can also find one of the values as 30-10 is what, similar is happening to this solution and at last, we will return the value of count.

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

Code

C++ code to count quadruples from four sorted arrays whose sum is equal to a given value x

#include <iostream>
#include<unordered_map>

using namespace std;

int getNumberOfQuadruples(int arr1[], int arr2[], int arr3[],int arr4[], int n, int x)
{
    int count = 0;

    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            MAP [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 (MAP.find(x - p_sum) != MAP.end())
                count += MAP [x - p_sum];
        }

    return count;
}
int main()
{
    int arr1[] = { 2, 5, 6, 9 };
    int arr2[] = { 1, 3, 7, 11 };
    int arr3[] = { 1, 5, 6, 8 };
    int arr4[] = { 2, 3, 5, 10 };

    int n = sizeof(arr1) / sizeof(arr1[0]);
    int x = 32;
    cout << "Count = "<< getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x);
    return 0;
}

Count = 3

Java code to count quadruples from four sorted arrays whose sum is equal to a given value x

import java.util.HashMap;

class QuadrupletsSum
{
    public static int getNumberOfQuadruples (int arr1[], int arr2[], int arr3[], int arr4[], int n, int x)
    {
        int count = 0;

        HashMap<Integer,Integer> MAP = new HashMap<>();

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if(MAP.containsKey(arr1[i] + arr2[j]))
                    MAP.put((arr1[i] + arr2[j]), MAP.get((arr1[i] + arr2[j]))+1);
                else
                    MAP.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 (MAP.containsKey(x - p_sum))
                    count += MAP.get(x - p_sum);
            }

        return count;
    }
    public static void main(String[] args)
    {
        int arr1[] = { 2, 5, 6, 9 };
        int arr2[] = { 1, 3, 7, 11 };
        int arr3[] = { 1, 5, 6, 8 };
        int arr4[] = { 2, 3, 5, 10 };

        int n = arr1.length;
        int x = 32;
        System.out.println("Count = "
                           + getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x));
    }
}

Count = 3

Complexity Analysis

Time Complexity

O(n2) where “n” is the number of elements in the array. We achieved polynomial time complexity of N^2 because we traversed only the elements from two arrays each time.

Space Complexity

O(n2) where “n” is the number of elements in the array. Since the number of elements being stored in the HashMap will be the elements from two arrays. We achieve quadratic space complexity.

Translate »