Find Three Element from Different Three Arrays such that A + B + C = Sum

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’
   
• Inside this loop, do the following operations:-  

       ✨Take temporary variable ‘x’ = ‘a2[i]’ + ‘a3[j]’

       ✨Check if ‘sum’ - ‘x’ is present in the map or not.

       ✨If present, print the triplet = ‘sum' - ‘x’, ‘a2[i]’, ‘a3[j]’.

       ✨If ‘flag’ = 0, return -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

Run Code

Output for C++✅

You can also read about the Longest Consecutive Sequence.

Code in Java💻👇

/* 
	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

Run Code

Output for Java✅

Code in Python3💻👇

"""
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

Run Code

Output for Python✅

Time and Space Complexity

We have used two sets of loops in the program.

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

int a[] = {1,2,4,5,1,2,4}
unordered_map<int, int>m;
for(int i=0;i<n;i++)
{
	m[a[i]]++;
}

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

Run Code

Conclusion

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:

• Check if an array can be divided into pairs whose sum is divisible by k
• Count divisible pairs in an array

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, Java Programming, and Operating System, etc. Have a look at the interview experiences and interview bundle for placement preparations. And also, enroll in our courses and refer to the mock test and problems available.

Do upvote our blog to help other ninjas grow.

Happy Learning!