In this article, we will discuss the problem to find three elements from different three arrays such that a + b + c = sum and briefly discuss the approach to be used and its time and space complexity.

Before discussing how to find three elements from different three arrays such that a + b + c = sum, letâ€™s first discuss what an array means.

Array: It is a linear data structure consisting of a collection of values called elements of an array, stored in a contiguous memory location, and can be accessed using array indexes.

In this problem, we are given three arrays of any size(provided by the user), and a number sum, and our task is to find three elements (say a,b,c) from these three arrays such that a + b + c = sum (given by the user).

Please donâ€™t get confused; letâ€™s understand the problem by an example.

Example:

In this example, we have three arrays, A1, A2, and A3, and the value of the variable, sum = 9. Most of the possible pairs are shown in the image below.

The approach is to store all the elements of the first array in an unordered map, subtract the sum of 2 elements from the remaining two arrays from the variable â€˜sumâ€™, and check if the resulting element is present in the unordered_map or not.

Algorithm

Take array size as input â€˜aâ€™, â€™bâ€™, â€™câ€™.

Create three arrays of size â€˜aâ€™, â€˜bâ€™, â€˜câ€™, let's say, â€˜a1[a]â€™, â€˜a2[b]â€™, â€˜a3[c]â€™.

Take a variable â€˜sumâ€™ input from the user.

Take an unordered map â€˜mâ€™.

Run a for loop from â€˜iâ€™ = 0 to â€˜a-1â€™ and store the frequency of elements in the map. To access any element in 0(1) time complexity.

Run another nested for loop from â€˜iâ€™ = 0 to â€˜b-1â€™ and j = 0 to â€˜c-1â€™

For example, the input arrays are Arr1[]={5,5,8,9} , Arr2[]={5,1,0}, Arr3[]={0,9,2} and the value of Sum = 10

So, firstly we will store the frequency of â€˜Arr1â€™ array elements in the hash table. So our resulting hash table will look like this:

After storing elements we have to iterate through the other two elements and perform the steps for each element of both arrays. Let's discuss each step in detail and see how pairs are created:-

For element Arr2[0] = 5, following iterations will be performed :

Similarly, for element Arr2[1] = 1

With Arr3[0] = 0 >> x = 1+0 >> sum - x = 10 - 1 >> Present - { 9, 1, 0 }

With Arr3[1] = 9 >> x = 1+9 >> sum - x = 10 -10 >> Not present in hash table.

With Arr3[2] = 2 >> x = 1+2 >> sum - x = 10 - 3 >> Not present in hash table.

Lastly, for element Arr2[2] = 0

With Arr3[0] = 0 >> x = 0+0 >> sum - x = 10 - 0 >> Not present in hash table.

With Arr3[1] = 9 >> x = 0+9 >> sum - x = 10 - 9 >> Not present in hash table.

With Arr3[2] = 2 >> x = 0+2 >> sum - x = 10 - 2 >> Present - { 8, 0, 2 }

So as a final result we have total 3 pairs - { 5, 5, 0 }, { 9, 1, 0 } and { 8, 0, 2 }.

Code in C++ðŸ’»ðŸ‘‡

/*
C++ program to find three elements from different three arrays such that a + b + c = sum
*/
#include<bits/stdc++.h>
using namespace std;
int findElements(int a1[], int a2[],int a3[], int a, int b, int c, int sum)
{
// Store frequency of elements of first array
unordered_map <int,int> m;
for (int i = 0; i < a; i++)
m[a1[i]]++;
// Sum of other two arrays element 1 by 1
int flag=0;
for (int i = 0; i < b; i++)
{
for (int j = 0; j < c; j++)
{
int x = a2[i] + a3[j];
if(m[sum -x] != 0)
{
flag++;
cout<<sum-x<<" "<<a2[i]<<" "<<a3[j]<<endl;
}
}
}
if(flag == 0)
return -1;
else
return flag;
}
// Driver Code
int main()
{
int a,b,c;
cout<<"\nEnter size of arrays : ";
cin>>a>>b>>c;
int a1[a], a2[b], a3[c];
cout<<"\nEnter 1st array elements : ";
for(int i=0;i<a;i++)
cin>>a1[i];
cout<<"\nEnter 2nd array elements : ";
for(int i=0;i<b;i++)
cin>>a2[i];
cout<<"\nEnter 3rd array elements : ";
for(int i=0;i<c;i++)
cin>>a3[i];
int sum;
cout<<"Enter sum value : ";
cin>>sum;
int flag = findElements(a1, a2, a3, a, b, c, sum);
if(flag == -1)
cout << "ANSWER : No, such triplet present...";
else
cout << "Total "<<flag<<" triplets found..";
return 0;
}

You can also try this code with Online C++ Compiler

/*
Java program to find three elements from different three arrays such that a + b + c = sum
*/
import java.util.*;
class Main
{
static int findElements(int a1[], int a2[], int a3[],int a, int b, int c, int sum)
{
// Store elements of first array in hash
HashSet<Integer> m = new HashSet<Integer>();
for (int i = 0; i < a; i++)
{
m.add(a1[i]);
}
// Sum of other two arrays element 1 by 1
int flag = 0;
ArrayList<Integer> al = new ArrayList<>(m);
for (int i = 0; i < b; i++)
{
for (int j = 0; j < c; j++)
{
int x = a2[i] + a3[j];
if (al.contains(sum - x) & al.indexOf(sum - x) != al.get(al.size() - 1))
{
flag++;
System.out.println(sum-x+" "+a2[i]+" "+a3[j]);
}
}
}
if(flag == 0)
return -1;
else
return flag;
}
// Driver Code
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.print("Enter size of arrays : ");
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
int a1[] = new int[a];
System.out.println("Enter elements of 1st array : ");
for(int i=0; i<a; i++)
{
a1[i] = sc.nextInt();
}
int a2[] = new int[b];
System.out.println("Enter elements of 2nd array : ");
for(int i=0; i<b; i++)
{
a2[i] = sc.nextInt();
}
int a3[] = new int[c];
System.out.println("Enter elements of 3rd array : ");
for(int i=0; i<c; i++)
{
a3[i] = sc.nextInt();
}
System.out.print("Enter sum value : ");
int sum=sc.nextInt();
int flag = findElements(a1, a2, a3, a, b, c, sum);
if (flag == -1)
System.out.println("ANSWER : No, such triplet present...");
else
System.out.println("Total "+flag+" triplets found..");
}
}

You can also try this code with Online Java Compiler

"""
Python3 program to find three elements from different three arrays such that a + b + c = sum
"""
def findElements(a1, a2, a3, a, b, c, summ):
# Store elements of first array in hash
m = set()
flag=0
for i in range(a):
m.add(a1[i])
# Sum of other two arrays element 1 by 1
for i in range(b):
for j in range(c):
if summ - a2[i] - a3[j] in m:
flag+=1
print(summ-a2[i]-a3[j], end="")
print(" ",a2[i]," ",a3[j])
if flag == 0:
return -1
else:
return flag
if __name__=='__main__':
a=int(input("Enter 1st array size : "))
b=int(input("Enter 2nd array size : "))
c=int(input("Enter 3rd array size : "))
a1=list(map(int, input("Enter 1st array elements : ").strip().split()))
a2=list(map(int, input("Enter 1st array elements : ").strip().split()))
a3=list(map(int, input("Enter 1st array elements : ").strip().split()))
summ = int(input("Enter sum value : "))
flag = findElements(a1, a2, a3, a, b, c, summ)
if flag == -1:
print("ANSWER : No, such triplet present...")
else:
print("Total ",flag," triplets found..")

You can also try this code with Online Python Compiler

One is a single for loop iterating from 0 to â€˜Aâ€™ to store the elements of one array in the hash, and This will take O(A) time complexity.

Another loop is a nested loop used to find the sum of each element of the last two arrays and search for the result in the first array stored in hash (that will take O(1) time), this loop iterates from 0 to â€˜Bâ€™ and â€˜0â€™ to â€˜Câ€™, and this will take O(B*C*N) time complexity.

If A = B = C, the whole program will take O(N*N) time.

ðŸŽ€ Total time complexity = O(N) + O(N*N) = O(N*N)

ðŸŽ€ Space Complexity = O(3xN) = O(N), for three arrays of size â€˜Nâ€™.

Frequently Asked Questions

What is an array?

An array is a collection of similar values stored at contiguous memory locations. It is like a staircase, where each value is placed at every step, and elements can be accessed by knowing the stair number (or index number).

What is Hashing?

Hashing is a technique using which a given value can be transformed into another value. It makes searching more accessible and quicker.

Mention differences between map and set?

Set is a collection of data that cannot contain duplicate elements, but the map is an interface used to store key-value pairs.

What is the complexity to find three elements from different three arrays such that a + b + c = sum?

The time complexity for this problem is O(N*N) and the space complexity is also O(N).

How can we calculate the frequency of elements in an array using a map?

For calculating the frequency, we need to iterate through every element of the array and add them to the map incrementing their previous values. Initially, a map is empty with all values assigned to zero. The code for the same is given below.

In this article, we see the implementation of the code to find three elements from different three arrays such that a + b + c = sum. We understood the problem using an example and discussed the algorithm, time and space complexity, and output of the program on user input using hashing.

If you want to learn more about such problems, visit the given links below: