Find three element from different three arrays such that that a + b + c = sum

Given three integer arrays and a “sum”, the task is to check if there are three elements a, b, c such that a + b + c = sum and a, b and c belong to three different arrays.

Examples :

Input : a1[] = { 1 , 2 , 3 , 4 , 5 };
    a2[] = { 2 , 3 , 6 , 1 , 2 };
    a3[] = { 3 , 2 , 4 , 5 , 6 };  
        sum = 9
Output : Yes
1  + 2  + 6 = 9  here 1 from a1[] and 2 from
a2[] and 6 from a3[]   
    
Input : a1[] = { 1 , 2 , 3 , 4 , 5 };
    a2[] = { 2 , 3 , 6 , 1 , 2 };
    a3[] = { 3 , 2 , 4 , 5 , 6 };   
         sum = 20 
Output : No

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A naive approach is to run three loops and check sum of three element form different arrays equal to given number if find then print exist and otherwise print not exist.

C++

// C++ program to find three element 
// from different three arrays such  
// that that a + b + c is equal to  
// given sum 
#include<bits/stdc++.h> 
using namespace std; 
  
// Function to check if there is  
// an element from each array such  
// that sum of the three elements  
// is equal to given sum. 
bool findTriplet(int a1[], int a2[],  
                 int a3[], int n1,  
                 int n2, int n3, int sum) 
{ 
    for (int i = 0; i < n1; i++) 
    for (int j = 0; j < n2; j++) 
        for (int k = 0; k < n3; k++) 
            if (a1[i] + a2[j] + a3[k] == sum) 
            return true; 
  
    return false; 
} 
  
// Driver Code 
int main() 
{ 
    int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
    int a2[] = { 2 , 3 , 6 , 1 , 2 }; 
    int a3[] = { 3 , 2 , 4 , 5 , 6 }; 
    int sum = 9; 
    int n1 = sizeof(a1) / sizeof(a1[0]); 
    int n2 = sizeof(a2) / sizeof(a2[0]); 
    int n3 = sizeof(a3) / sizeof(a3[0]); 
    findTriplet(a1, a2, a3, n1, n2, n3, sum)? 
                cout << "Yes" : cout << "No"; 
    return 0; 
} 

Java

// Java program to find three element 
// from different three arrays such  
// that that a + b + c is equal to  
// given sum 
class GFG  
{ 
          
    // Function to check if there is 
    // an element from each array such  
    // that sum of the three elements 
    // is equal to given sum. 
    static boolean findTriplet(int a1[], int a2[],  
                               int a3[], int n1,  
                               int n2, int n3, int sum) 
    { 
        for (int i = 0; i < n1; i++) 
            for (int j = 0; j < n2; j++) 
                for (int k = 0; k < n3; k++) 
                    if (a1[i] + a2[j] + a3[k] == sum) 
                    return true; 
      
        return false; 
    } 
      
    // Driver code 
    public static void main (String[] args) 
    { 
        int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
        int a2[] = { 2 , 3 , 6 , 1 , 2 }; 
        int a3[] = { 3 , 2 , 4 , 5 , 6 }; 
        int sum = 9; 
          
        int n1 = a1.length; 
        int n2 = a2.length; 
        int n3 = a3.length; 
          
        if(findTriplet(a1, a2, a3, n1, n2, n3, sum)) 
            System.out.print("Yes"); 
        else
            System.out.print("No"); 
    } 
} 
  
// This code is contributed by Anant Agarwal. 

Python3

# Python3 program to find  
# three element from different  
# three arrays such that that  
# a + b + c is equal to  
# given sum 
  
# Function to check if there  
# is an element from each  
# array such that sum of the  
# three elements is equal to  
# given sum. 
def findTriplet(a1, a2, a3,  
                n1, n2, n3, sum): 
  
    for i in range(0 , n1): 
        for j in range(0 , n2): 
            for k in range(0 , n3): 
                if (a1[i] + a2[j] + 
                    a3[k] == sum): 
                    return True
  
    return False
  
# Driver Code 
a1 = [ 1 , 2 , 3 , 4 , 5 ] 
a2 = [ 2 , 3 , 6 , 1 , 2 ] 
a3 = [ 3 , 2 , 4 , 5 , 6 ] 
sum = 9
n1 = len(a1) 
n2 = len(a2) 
n3 = len(a3)  
print("Yes") if findTriplet(a1, a2, a3,  
                            n1, n2, n3,  
                            sum) else print("No") 
  
# This code is contributed  
# by Smitha 

C#

// C# program to find three element  
// from different three arrays such 
// that that a + b + c is equal to 
// given sum 
using System; 
  
public class GFG 
{ 
  
// Function to check if there is an  
// element from each array such that 
// sum of the three elements is  
// equal to given sum. 
static bool findTriplet(int []a1, int []a2, 
                        int []a3, int n1,  
                        int n2, int n3,  
                        int sum) 
{ 
      
    for (int i = 0; i < n1; i++) 
      
        for (int j = 0; j < n2; j++) 
          
            for (int k = 0; k < n3; k++) 
            if (a1[i] + a2[j] + a3[k] == sum) 
            return true; 
  
    return false; 
} 
  
    // Driver Code 
    static public void Main () 
    { 
        int []a1 = {1 , 2 , 3 , 4 , 5}; 
        int []a2 = {2 , 3 , 6 , 1 , 2}; 
        int []a3 = {3 , 2 , 4 , 5 , 6}; 
        int sum = 9; 
        int n1 = a1.Length; 
        int n2 = a2.Length; 
        int n3 = a3.Length; 
        if(findTriplet(a1, a2, a3, n1, 
                       n2, n3, sum)) 
        Console.WriteLine("Yes"); 
        else
        Console.WriteLine("No"); 
    } 
} 
  
// This code is contributed by vt_m. 

PHP

<?php 
// PHP program to find three element  
// from different three arrays such  
// that that a + b + c is equal to  
// given sum 
  
// Function to check if there is an  
// element from each array such that  
// sum of the three elements is equal 
// to given sum. 
function findTriplet($a1, $a2, $a3,  
                     $n1, $n2, $n3,  
                     $sum) 
{ 
    for ( $i = 0; $i < $n1; $i++) 
    for ( $j = 0; $j < $n2; $j++) 
        for ( $k = 0; $k < $n3; $k++) 
            if ($a1[$i] + $a2[$j] + $a3[$k] == $sum) 
            return true; 
  
    return false; 
} 
  
// Driver Code 
$a1 = array( 1 , 2 , 3 , 4 , 5 ); 
$a2 = array( 2 , 3 , 6 , 1 , 2 ); 
$a3 = array( 3 , 2 , 4 , 5 , 6 ); 
$sum = 9; 
$n1 = count($a1); 
$n2 = count($a2); 
$n3 = count($a3); 
if(findTriplet($a1, $a2, $a3, $n1,  
               $n2, $n3, $sum)==true) 
echo "Yes" ; 
else
echo "No"; 
  
// This code is contributed by anuj_67. 
?> 

Output :

Yes

Time complexity : O(n³)
Space complexity : O(1)

An efficient solution is to store all elements of first array in hash table (unordered_set in C++) and calculate sum of two elements last two array elements one by one and substract from given number k and check in hash table if it’s exist in hash table then print exist and otherwise not exist.

1. Store all elements of first array in hash table
2. Generate all pairs of elements from two arrays using
   nested loop. For every pair (a1[i], a2[j]), check if
   sum - (a1[i] + a2[j]) exists in hash table. If yes
   return true.

Below is the implementation of above idea.

C++

// C++ program to find three element  
// from different three arrays such  
// that that a + b + c is equal to 
// given sum 
#include<bits/stdc++.h> 
using namespace std; 
  
// Function to check if there is 
// an element from each array such  
// that sum of the three elements is 
// equal to given sum. 
bool findTriplet(int a1[], int a2[],  
                 int a3[], int n1,  
                 int n2, int n3,  
                 int sum) 
{ 
    // Store elements of 
    // first array in hash 
    unordered_set <int> s; 
    for (int i = 0; i < n1; i++) 
        s.insert(a1[i]); 
  
    // sum last two arrays  
    // element one by one 
    for (int i = 0; i < n2; i++) 
    { 
        for (int j = 0; j < n3; j++) 
        { 
            // Consider current pair and  
            // find if there is an element  
            // in a1[] such that these three 
            // form a required triplet 
            if (s.find(sum - a2[i] - a3[j]) !=  
                                       s.end()) 
                return true; 
        } 
    } 
  
    return false; 
} 
  
// Driver Code 
int main() 
{ 
    int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
    int a2[] = { 2 , 3 , 6 , 1 , 2 }; 
    int a3[] = { 3 , 2 , 4 , 5 , 6 }; 
    int sum = 9; 
    int n1 = sizeof(a1) / sizeof(a1[0]); 
    int n2 = sizeof(a2) / sizeof(a2[0]); 
    int n3 = sizeof(a3) / sizeof(a3[0]); 
    findTriplet(a1, a2, a3, n1, n2, n3, sum)? 
    cout << "Yes" : cout << "No"; 
  
    return 0; 
} 

Java

// Java program to find three element  
// from different three arrays such  
// that that a + b + c is equal to 
// given sum 
import java.util.*; 
  
class GFG  
{ 
  
    // Function to check if there is 
    // an element from each array such  
    // that sum of the three elements is 
    // equal to given sum. 
    static boolean findTriplet(int a1[], int a2[], int a3[], 
                                int n1, int n2, int n3, 
                                int sum) 
    { 
        // Store elements of 
        // first array in hash 
        HashSet<Integer> s = new HashSet<Integer>(); 
        for (int i = 0; i < n1; i++)  
        { 
            s.add(a1[i]); 
        } 
  
        // sum last two arrays  
        // element one by one 
        ArrayList<Integer> al = new ArrayList<>(s); 
        for (int i = 0; i < n2; i++)  
        { 
            for (int j = 0; j < n3; j++)  
            { 
                  
                // Consider current pair and  
                // find if there is an element  
                // in a1[] such that these three 
                // form a required triplet 
                if (al.contains(sum - a2[i] - a3[j]) &  
                            al.indexOf(sum - a2[i] - a3[j]) 
                            != al.get(al.size() - 1))  
                { 
                    return true; 
                } 
            } 
        } 
        return false; 
    } 
  
    // Driver Code 
    public static void main(String[] args)  
    { 
        int a1[] = {1, 2, 3, 4, 5}; 
        int a2[] = {2, 3, 6, 1, 2}; 
        int a3[] = {3, 2, 4, 5, 6}; 
        int sum = 9; 
        int n1 = a1.length; 
        int n2 = a2.length; 
        int n3 = a3.length; 
        if (findTriplet(a1, a2, a3, n1, n2, n3, sum))  
        { 
            System.out.println("Yes"); 
        } 
        else
        { 
            System.out.println("No"); 
        } 
    } 
}  
  
// This code is contributed by 29AjayKumar 

Python3

# Python3 program to find three element  
# from different three arrays such  
# that that a + b + c is equal to  
# given sum  
  
# Function to check if there is  
# an element from each array such  
# that sum of the three elements is  
# equal to given sum.  
def findTriplet(a1, a2, a3,  
                n1, n2, n3, sum): 
  
    # Store elements of first  
    # array in hash  
    s = set() 
  
    # sum last two arrays element  
    # one by one  
    for i in range(n1): 
        s.add(a1[i]) 
  
    for i in range(n2): 
        for j in range(n3): 
  
            # Consider current pair and  
            # find if there is an element  
            # in a1[] such that these three  
            # form a required triplet  
            if sum - a2[i] - a3[j] in s: 
                return True
    return False
  
# Driver code 
a1 = [1, 2, 3, 4, 5] 
a2 = [2, 3, 6, 1, 2] 
a3 = [3, 24, 5, 6] 
n1 = len(a1) 
n2 = len(a2) 
n3 = len(a3) 
sum = 9
if findTriplet(a1, a2, a3,  
               n1, n2, n3, sum) == True: 
    print("Yes") 
else: 
    print("No") 
  
# This code is contributed by Shrikant13 

C#

// C# program to find three element  
// from different three arrays such  
// that that a + b + c is equal to 
// given sum 
using System; 
using System.Collections.Generic; 
  
class GFG  
{ 
  
    // Function to check if there is 
    // an element from each array such  
    // that sum of the three elements is 
    // equal to given sum. 
    static bool findTriplet(int []a1, int []a2, int []a3, 
                                int n1, int n2, int n3, 
                                int sum) 
    { 
        // Store elements of 
        // first array in hash 
        HashSet<int> s = new HashSet<int>(); 
        for (int i = 0; i < n1; i++)  
        { 
            s.Add(a1[i]); 
        } 
  
        // sum last two arrays  
        // element one by one 
        List<int> al = new List<int>(s); 
        for (int i = 0; i < n2; i++)  
        { 
            for (int j = 0; j < n3; j++)  
            { 
                  
                // Consider current pair and  
                // find if there is an element  
                // in a1[] such that these three 
                // form a required triplet 
                if (al.Contains(sum - a2[i] - a3[j]) &  
                            al.IndexOf(sum - a2[i] - a3[j]) 
                            != al[al.Count - 1])  
                { 
                    return true; 
                } 
            } 
        } 
        return false; 
    } 
  
    // Driver Code 
    public static void Main(String[] args)  
    { 
        int []a1 = {1, 2, 3, 4, 5}; 
        int []a2 = {2, 3, 6, 1, 2}; 
        int []a3 = {3, 2, 4, 5, 6}; 
        int sum = 9; 
        int n1 = a1.Length; 
        int n2 = a2.Length; 
        int n3 = a3.Length; 
        if (findTriplet(a1, a2, a3, n1, n2, n3, sum))  
        { 
            Console.WriteLine("Yes"); 
        } 
        else
        { 
            Console.WriteLine("No"); 
        } 
    } 
} 
  
// This code is contributed by PrinciRaj1992 

Output :

Yes

Time complexity : O(n²)
Auxiliary Space : O(n)

References :
http://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-a-given-number

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Find three element from different three arrays such that that a + b + c = sum

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

C++

Java

Python3

C#

PHP

C++

Java

Python3

C#

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books