Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
3.
Algorithm
4.
Code in C++💻👇
4.1.
Output for C++✅
5.
Code in Java💻👇
5.1.
Output for Java✅
6.
Code in Python3💻👇
6.1.
Output for Python✅
7.
Time and Space Complexity
8.
Frequently Asked Questions
8.1.
What is an array?
8.2.
What is Hashing?
8.3.
Mention differences between map and set?
8.4.
What is the complexity to find three elements from different three arrays such that a + b + c = sum?
8.5.
How can we calculate the frequency of elements in an array using a map?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Author Ayushi Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

Topic name

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.

Example for understanding

Also Read About, Hash Function in Data Structure.

Approach

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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: 

resultant hash table

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 : 

1st iteration

2nd iteration

3rd iteration

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;
}

Output for C++

C++ Code Output


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..");
	}
}

Output for Java

Java code output

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

Output for Python✅

Python code output

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]]++;
}

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:

 

Recommended problems -

 

Thank you 

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!

Previous article
Check if a given array contains duplicate elements within k distance from each other
Next article
Find Pairs of Positive and Negative Values Present in a Given Array
Live masterclass