Tutorialspoint.dev

Given two unsorted arrays, find all pairs whose sum is x

Given two unsorted arrays of distinct elements, the task is to find all pairs from both arrays whose sum is equal to x.

Examples:

Input :  arr1[] = {-1, -2, 4, -6, 5, 7}
         arr2[] = {6, 3, 4, 0}  
         x = 8
Output : 4 4
         5 3

Input : arr1[] = {1, 2, 4, 5, 7} 
        arr2[] = {5, 6, 3, 4, 8}  
        x = 9
Output : 1 8
         4 5
         5 4

Asked in : Amazon


A Naive approach is to simply run two loops and pick elements from both arrays. One by one check that both elements sum is equal to given value x or not.

C++



// C++ program to find all pairs in both arrays
// whose sum is equal to given value x
#include<bits/stdc++.h>
  
using namespace std;
  
// Function to print all pairs in both arrays
// whose sum is equal to given value x
void findPairs(int arr1[], int arr2[], int n,
                               int m, int x)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (arr1[i] + arr2[j] == x)
                cout << arr1[i] << " "
                     << arr2[j] << endl;
}
  
// Driver code
int main()
{
    int arr1[] = {1, 2, 3, 7, 5, 4};
    int arr2[] = {0, 7, 4, 3, 2, 1};
    int n = sizeof(arr1)/sizeof(int);
    int m = sizeof(arr2)/sizeof(int);
    int x = 8;
    findPairs(arr1, arr2, n, m, x);
    return 0;
}

Java

// Java program to find all pairs in both arrays
// whose sum is equal to given value x
import java.io.*;
  
class GFG 
{
  
    // Function to print all pairs in both arrays
    // whose sum is equal to given value x
    static void findPairs(int arr1[], int arr2[], int n,
                                           int m, int x)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (arr1[i] + arr2[j] == x)
                    System.out.println( arr1[i] + " "
                                           + arr2[j] );
    }
  
    // Driver code
    public static void main(String[] args) 
    {
        int arr1[] = {1, 2, 3, 7, 5, 4};
        int arr2[] = {0, 7, 4, 3, 2, 1};
        int x = 8;
        findPairs(arr1, arr2, arr1.length, arr2.length, x);
    }
  
}
  
// This code is contributed 
// by sunnysingh

Python3

# Python 3 program to find all 
# pairs in both arrays whose 
# sum is equal to given value x
  
# Function to print all pairs 
# in both arrays whose sum is
# equal to given value x
def findPairs(arr1, arr2, n, m, x):
  
    for i in range(0, n):
        for j in range(0, m):
            if (arr1[i] + arr2[j] == x):
                print(arr1[i], arr2[j])
  
# Driver code
arr1 = [1, 2, 3, 7, 5, 4]
arr2 = [0, 7, 4, 3, 2, 1]
n = len(arr1)
m = len(arr2)
x = 8
findPairs(arr1, arr2, n, m, x)
  
# This code is contributed by Smitha Dinesh Semwal

C#

// C# program to find all 
// pairs in both arrays
// whose sum is equal to 
// given value x
using System;
  
class GFG
{
  
// Function to print all 
// pairs in both arrays
// whose sum is equal to
// given value x
static void findPairs(int []arr1, int []arr2, 
                      int n, int m, int x)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (arr1[i] + arr2[j] == x)
                Console.WriteLine(arr1[i] + " " +
                                       arr2[j] );
}
  
// Driver code
static void Main()
{
    int []arr1 = {1, 2, 3, 7, 5, 4};
    int []arr2 = {0, 7, 4, 3, 2, 1};
    int x = 8;
    findPairs(arr1, arr2, 
              arr1.Length, 
              arr2.Length, x);
}
}
  
// This code is contributed 
// by Sam007

PHP

<?php
// PHP program to find all pairs 
// in both arrays whose sum is 
// equal to given value x
  
// Function to print all pairs 
// in both arrays whose sum is
// equal to given value x
function findPairs($arr1, $arr2
                   $n, $m, $x)
{
    for ($i = 0; $i < $n; $i++)
        for ($j = 0; $j < $m; $j++)
            if ($arr1[$i] + $arr2[$j] == $x)
                echo $arr1[$i] . " "
                     $arr2[$j] . " ";
  
// Driver code
$arr1 = array(1, 2, 3, 7, 5, 4);
$arr2 = array(0, 7, 4, 3, 2, 1);
$n = count($arr1);
$m = count($arr2);
$x = 8;
findPairs($arr1, $arr2
          $n, $m, $x);
  
// This code is contributed 
// by Sam007
?>


Output:

1 7
7 1
5 3
4 4

Time Complexity : O(n^2)
Auxiliary Space : O(1)

An Efficient solution of this problem is to hashing. Hash table is implemented using unordered_set in C++. We store all first array elements in hash table. For elements of second array, we subtract every element from x and check the result in hash table. If result is present, we print the element and key in hash (which is an element of first array).

C++

// C++ program to find all pair in both arrays
// whose sum is equal to given value x
#include<bits/stdc++.h>
using namespace std;
  
// Function to find all pairs in both arrays
// whose sum is equal to given value x
void findPairs(int arr1[], int arr2[], int n,
                               int m, int x)
{
    // Insert all elements of first array in a hash
    unordered_set<int> s;
    for (int i = 0; i < n; i++)
        s.insert(arr1[i]);
  
    // Subtract sum from second array elements one
    // by one and check it's present in array first
    // or not
    for (int j = 0; j < m; j++)
        if (s.find(x - arr2[j]) != s.end())
            cout << x-arr2[j] << " "
                 << arr2[j] << endl;
}
  
// Driver code
int main()
{
    int arr1[] = {1, 0, -4, 7, 6, 4};
    int arr2[] = {0 ,2, 4, -3, 2, 1};
    int x = 8;
    int n = sizeof(arr1)/sizeof(int);
    int m = sizeof(arr2)/sizeof(int);
    findPairs(arr1, arr2, n, m, x);
    return 0;
}

Java

// JAVA Code for Given two unsorted arrays, 
// find all pairs whose sum is x
import java.util.*;
  
class GFG {
  
     // Function to find all pairs in both arrays
    // whose sum is equal to given value x
    public static void findPairs(int arr1[], int arr2[],
                                 int n, int m, int x)
    {
        // Insert all elements of first array in a hash
        HashMap<Integer, Integer> s = new HashMap<Integer, Integer>();
          
        for (int i = 0; i < n; i ++)
            s.put(arr1[i], 0);
       
        // Subtract sum from second array elements one
        // by one and check it's present in array first
        // or not
        for (int j = 0; j < m; j ++)
            if (s.containsKey(x - arr2[j]))
                System.out.println(x - arr2[j] + " " + arr2[j]);             
    }
      
    /* Driver program to test above function */
    public static void main(String[] args) 
    {
        int arr1[] = {1, 0, -4, 7, 6, 4};
        int arr2[] = {0 ,2, 4, -3, 2, 1};
        int x = 8;
          
        findPairs(arr1, arr2, arr1.length, arr2.length, x);
       
    }
  }
// This code is contributed by Arnav Kr. Mandal.

Python3

# Python3 program to find all 
# pair in both arrays whose 
# sum is equal to given value x
  
# Function to find all pairs 
# in both arrays whose sum is
# equal to given value x
def findPairs(arr1, arr2, n, m, x):
  
    # Insert all elements of 
    # first array in a hash
    s = set()
    for i in range (0, n):
        s.add(arr1[i])
  
    # Subtract sum from second 
    # array elements one by one 
    # and check it's present in
    # array first or not
    for j in range(0, m):
        if ((x - arr2[j]) in s):
            print((x - arr2[j]), '', arr2[j])
  
# Driver code
arr1 = [1, 0, -4, 7, 6, 4]
arr2 = [0, 2, 4, -3, 2, 1]
x = 8
  
n = len(arr1)
m = len(arr2)
findPairs(arr1, arr2, n, m, x)
  
# This code is contributed 
# by ihritik

C#

// C# Code for Given two unsorted arrays, 
// find all pairs whose sum is x 
using System;
using System.Collections.Generic;
  
class GFG
{
  
// Function to find all pairs in 
// both arrays whose sum is equal
// to given value x 
public static void findPairs(int[] arr1, int[] arr2, 
                             int n, int m, int x)
{
    // Insert all elements of first
    // array in a hash 
    Dictionary<int
               int> s = new Dictionary<int
                                       int>();
  
    for (int i = 0; i < n; i++)
    {
        s[arr1[i]] = 0;
    }
  
    // Subtract sum from second array 
    // elements one by one and check
    // it's present in array first 
    // or not 
    for (int j = 0; j < m; j++)
    {
        if (s.ContainsKey(x - arr2[j]))
        {
            Console.WriteLine(x - arr2[j] + 
                            " " + arr2[j]);
        }
    }
}
  
// Driver Code
public static void Main(string[] args)
{
    int[] arr1 = new int[] {1, 0, -4, 7, 6, 4};
    int[] arr2 = new int[] {0, 2, 4, -3, 2, 1};
    int x = 8;
  
    findPairs(arr1, arr2, arr1.Length, 
                          arr2.Length, x);
}
}
  
// This code is contributed by Shrikant13


Output:

6 2
4 4
6 2
7 1

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

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter