Find three element from different three arrays such that A + B + C = sum

In this article, We will discuss the problem to find three elements from different three arrays such that A + B + C = sum.  Consider the below example for a better understanding.

Let’s assume A, B, and C are 3 arrays of “N” elements each. Now your task is to find a way for determining whether there exists an a in A, b in B, and c in C such that a+b+c = sum.

Consider the below example,

Example-1:

Input : 

    A[] = { 1 , 2 , 3 , 4 , 5 };
    B[] = { 2 , 3 , 6 , 1 , 2 };
    C[] = { 3 , 2 , 4 , 5 , 6 };  
        
    
sum = 9

Output : Yes


Explanation: 

1  + 2  + 6 = 9  here 1 from A[] and 2 from
B[] and 6 from C[]

 

Example-2:

Input : 

    A[] = { 1 , 2 , 3 , 4 , 5 };
    B[] = { 2 , 3 , 6 , 1 , 2 };
    C[] = { 3 , 2 , 4 , 5 , 6 };   
 
sum = 120 

Output : No 


Explanation:
 
Never be the sum of three array index value will be 120.

 

The primary prerequisites to understanding this C/C++ Program:

 

Naive Approach:

It is the simplest approach to find three elements from different three arrays such that A + B + C = sum. But the cost is performance, so it is not advisable.

In this approach, you need to run three loops and check the sum of three elements of the different arrays equals the given number or not. If equal then simply break all three loops and print the message “Yes”.

/*
C++ program to Find Three Element
From Different Three Arrays Such
That a + b + c = sum
*/
#include<bits/stdc++.h>
using namespace std;


bool findVariantOf3Sum(int A[], int B[],
                       int C[], const int N1,
                       const int N2, const int N3, const int sum)
{
    bool isFind = false;
    for (int i = 0; ((i < N1) && !isFind); i++)
    {
        for (int j = 0; ((j < N2) && !isFind); j++)
        {
            for (int k = 0; ((k < N3) && !isFind); k++)
            {
                const int addValue = A[i] + B[j] + C[k];
                isFind = (addValue == sum);
            }
        }
    }
    return isFind;
}


int main()
{
    int A[] = { 1, 2, 3, 4, 5 };
    int B[] = { 2, 3, 6, 1, 2 };
    int C[] = { 3, 2, 4, 5, 6 };

    const int sum = 9;

    const int N1 = sizeof(A) / sizeof(A[0]);
    const int N2 = sizeof(B) / sizeof(B[0]);
    const int N3 = sizeof(C) / sizeof(C[0]);


    const bool isFind = findVariantOf3Sum(A, B, C, N1, N2, N3, sum);

    //print the result
    cout << (isFind ? "Yes":"No");

    return 0;
}

Output: “Yes”

Time Complexity: O(n3)
Auxiliary Space: O(1)

 

Efficient Approach:

Using the unordered_set (stores only unique elements) you can write the program efficiently. In this solution, we store all the elements of the first array in the data container and calculate the sum of two elements of the last two array elements one by one and subtract from the given number “sum” and check the data container. If it exists in the data container then print “Yes” otherwise “No”.

/*
C++ program to Find Three Element
From Different Three Arrays Such
That a + b + c = sum
*/
#include<bits/stdc++.h>
using namespace std;


bool findVariantOf3Sum(int A[], int B[],
                       int C[], const int N1,
                       const int N2, const int N3,
                       const int sum)
{
    /*
      Store unique elements of array
      A in no particular order.
    */
    unordered_set <int> arr;
    for (int i = 0; i < N1; i++)
    {
        arr.insert(A[i]);
    }

    bool isFind = false;

    /*
     sum last two arrays
     element one by one
     */
    for (int i = 0; ((i < N2) && (!isFind)); i++)
    {
        for (int j = 0; ((j < N3) && (!isFind)) ; j++)
        {
            /*
            Consider the pair (i,j) and
                     find if there is an element
                     in A[] such that a+b+c = sum
            */
            if (arr.find(sum - B[i] - C[j]) !=
                    arr.end())
            {
                isFind = true;
            }

        }
    }

    return isFind;
}


int main()
{
    int A[] = { 1, 2, 3, 4, 5 };
    int B[] = { 2, 3, 6, 1, 2 };
    int C[] = { 3, 2, 4, 5, 6 };

    int sum = 7;

    const int N1 = sizeof(A) / sizeof(A[0]);
    const int N2 = sizeof(B) / sizeof(B[0]);
    const int N3 = sizeof(C) / sizeof(C[0]);

    const bool isFind = findVariantOf3Sum(A, B, C, N1, N2, N3, sum);

    //print the result
    cout << (isFind ? "Yes":"No");

    return 0;
}

Output: “Yes”

Time Complexity: O(n2)
Auxiliary Space: O(n)

 

Recommended Articles for you: