Given a Set of Numbers Find Solution

Given an array of integers, find anyone combination of four elements in the array whose sum is equal to a given value X.

For example,

Become a success story instead of just reading about them. Prepare for coding interviews at Amazon and other top product-based companies with our Amazon Test Series. Includes topic-wise practice questions on all important DSA topics along with 10 practice contests of 2 hours each. Designed by industry experts that will surely help you practice and sharpen your programming skills. Wait no more, start your preparation today!

          Input:          array = {10, 2, 3, 4, 5, 9, 7, 8}         X = 23          Output:          3 5 7 8 Sum of output is equal to 23,  i.e. 3 + 5 + 7 + 8 = 23.          Input:          array = {1, 2, 3, 4, 5, 9, 7, 8}        X = 16          Output:          1 3 5 7 Sum of output is equal to 16,  i.e. 1 + 3 + 5 + 7 = 16.

We have discussed an O(n³) algorithm in the previous post on this topic. The problem can be solved in O(n² Logn) time with the help of auxiliary space.
Thanks to itsnimish for suggesting this method. Following is the detailed process.

Method 1: Two Pointers Algorithm.
Approach: Let the input array be A[].

Create an auxiliary array aux[] and store sum of all possible pairs in aux[]. The size of aux[] will be n*(n-1)/2 where n is the size of A[].
Sort the auxiliary array aux[].
Now the problem reduces to find two elements in aux[] with sum equal to X. We can use method 1 of this post to find the two elements efficiently. There is following important point to note though:
An element of aux[] represents a pair from A[]. While picking two elements from aux[], we must check whether the two elements have an element of A[] in common. For example, if first element sum of A[1] and A[2], and second element is sum of A[2] and A[4], then these two elements of aux[] don't represent four distinct elements of input array A[].

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

class pairSum {

public :

int first;

int sec;

int sum;

};

int compare( const void * a, const void * b)

{

return ((*(pairSum*)a).sum - (*(pairSum*)b).sum);

}

bool noCommon(pairSum a, pairSum b)

{

if (a.first == b.first || a.first == b.sec

|| a.sec == b.first || a.sec == b.sec)

return false ;

return true ;

}

void findFourElements( int arr[], int n, int X)

{

int i, j;

int size = (n * (n - 1)) / 2;

pairSum aux[size];

int k = 0;

for (i = 0; i < n - 1; i++) {

for (j = i + 1; j < n; j++) {

aux[k].sum = arr[i] + arr[j];

aux[k].first = i;

aux[k].sec = j;

k++;

}

qsort (aux, size, sizeof (aux[0]), compare);

i = 0;

j = size - 1;

while (i < size && j >= 0) {

if ((aux[i].sum + aux[j].sum == X)

&& noCommon(aux[i], aux[j])) {

cout << arr[aux[i].first] << ", "

<< arr[aux[i].sec] << ", "

<< arr[aux[j].first] << ", "

<< arr[aux[j].sec] << endl;

return ;

}

else if (aux[i].sum + aux[j].sum < X)

i++;

else

j--;

}

int main()

{

int arr[] = { 10, 20, 30, 40, 1, 2 };

int n = sizeof (arr) / sizeof (arr[0]);

int X = 91;

findFourElements(arr, n, X);

return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

struct pairSum {

int first;

int sec;

int sum;

};

int compare( const void * a, const void * b)

{

return ((*(pairSum*)a).sum - (*(pairSum*)b).sum);

}

bool noCommon( struct pairSum a, struct pairSum b)

{

if (a.first == b.first || a.first == b.sec

|| a.sec == b.first || a.sec == b.sec)

return false ;

return true ;

}

void findFourElements( int arr[], int n, int X)

{

int i, j;

int size = (n * (n - 1)) / 2;

struct pairSum aux[size];

int k = 0;

for (i = 0; i < n - 1; i++) {

for (j = i + 1; j < n; j++) {

aux[k].sum = arr[i] + arr[j];

aux[k].first = i;

aux[k].sec = j;

k++;

}

qsort (aux, size, sizeof (aux[0]), compare);

i = 0;

j = size - 1;

while (i < size && j >= 0) {

if ((aux[i].sum + aux[j].sum == X)

&& noCommon(aux[i], aux[j])) {

printf ( "%d, %d, %d, %d\n" , arr[aux[i].first],

arr[aux[i].sec], arr[aux[j].first],

arr[aux[j].sec]);

return ;

}

else if (aux[i].sum + aux[j].sum < X)

i++;

else

j--;

}

int main()

{

int arr[] = { 10, 20, 30, 40, 1, 2 };

int n = sizeof (arr) / sizeof (arr[0]);

int X = 91;

findFourElements(arr, n, X);

return 0;

}

Please note that the above code prints only one quadruple. If we remove the return statement and add statements "i++; j–;", then it prints same quadruple five times. The code can modified to print all quadruples only once. It has been kept this way to keep it simple.
Complexity Analysis:

Time complexity: O(n^2Logn).
The step 1 takes O(n^2) time. The second step is sorting an array of size O(n^2). Sorting can be done in O(n^2Logn) time using merge sort or heap sort or any other O(nLogn) algorithm. The third step takes O(n^2) time. So overall complexity is O(n^2Logn).
Auxiliary Space: O(n^2).
The size of the auxiliary array is O(n^2). The big size of the auxiliary array can be a concern in this method.

Method 2: Hashing Based Solution[O(n²)]

Approach:

Store sums of all pairs in a hash table
Traverse through all pairs again and search for X – (current pair sum) in the hash table.
If a pair is found with the required sum, then make sure that all elements are distinct array elements and an element is not considered more than once.

Below image is a dry run of the above approach:

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void findFourElements( int arr[], int n, int X)

{

unordered_map< int , pair< int , int > > mp;

for ( int i = 0; i < n - 1; i++)

for ( int j = i + 1; j < n; j++)

mp[arr[i] + arr[j]] = { i, j };

for ( int i = 0; i < n - 1; i++) {

for ( int j = i + 1; j < n; j++) {

int sum = arr[i] + arr[j];

if (mp.find(X - sum) != mp.end()) {

pair< int , int > p = mp[X - sum];

if (p.first != i && p.first != j

&& p.second != i && p.second != j) {

cout << arr[i] << ", " << arr[j] << ", "

<< arr[p.first] << ", "

<< arr[p.second];

return ;

}

int main()

{

int arr[] = { 10, 20, 30, 40, 1, 2 };

int n = sizeof (arr) / sizeof (arr[0]);

int X = 91;

findFourElements(arr, n, X);

return 0;

}

Java

import java.util.HashMap;

class GFG {

static class pair {

int first, second;

public pair( int first, int second)

{

this .first = first;

this .second = second;

}

static void findFourElements( int arr[], int n, int X)

{

HashMap<Integer, pair> mp

= new HashMap<Integer, pair>();

for ( int i = 0 ; i < n - 1 ; i++)

for ( int j = i + 1 ; j < n; j++)

mp.put(arr[i] + arr[j], new pair(i, j));

for ( int i = 0 ; i < n - 1 ; i++) {

for ( int j = i + 1 ; j < n; j++) {

int sum = arr[i] + arr[j];

if (mp.containsKey(X - sum)) {

pair p = mp.get(X - sum);

if (p.first != i && p.first != j

&& p.second != i && p.second != j) {

System.out.print(

arr[i] + ", " + arr[j] + ", "

+ arr[p.first] + ", "

+ arr[p.second]);

return ;

}

public static void main(String[] args)

{

int arr[] = { 10 , 20 , 30 , 40 , 1 , 2 };

int n = arr.length;

int X = 91 ;

findFourElements(arr, n, X);

}

Python3

def findFourElements(arr, n, X):

mp = {}

for i in range (n - 1 ):

for j in range (i + 1 , n):

mp[arr[i] + arr[j]] = [i, j]

for i in range (n - 1 ):

for j in range (i + 1 , n):

summ = arr[i] + arr[j]

if (X - summ) in mp:

p = mp[X - summ]

if (p[ 0 ] ! = i and p[ 0 ] ! = j and p[ 1 ] ! = i and p[ 1 ] ! = j):

print (arr[i], ", " , arr[j], ", " ,

arr[p[ 0 ]], ", " , arr[p[ 1 ]], sep = "")

return

arr = [ 10 , 20 , 30 , 40 , 1 , 2 ]

n = len (arr)

X = 91

findFourElements(arr, n, X)

C#

using System;

using System.Collections.Generic;

class GFG {

public class pair {

public int first, second;

public pair( int first, int second)

{

this .first = first;

this .second = second;

}

static void findFourElements( int [] arr, int n, int X)

{

Dictionary< int , pair> mp

= new Dictionary< int , pair>();

for ( int i = 0; i < n - 1; i++)

for ( int j = i + 1; j < n; j++)

if (mp.ContainsKey(arr[i] + arr[j]))

mp[arr[i] + arr[j]] = new pair(i, j);

else

mp.Add(arr[i] + arr[j], new pair(i, j));

for ( int i = 0; i < n - 1; i++) {

for ( int j = i + 1; j < n; j++) {

int sum = arr[i] + arr[j];

if (mp.ContainsKey(X - sum)) {

pair p = mp[X - sum];

if (p.first != i && p.first != j

&& p.second != i && p.second != j) {

Console.Write(arr[i] + ", " + arr[j]

+ ", " + arr[p.first]

+ ", "

+ arr[p.second]);

return ;

}

public static void Main(String[] args)

{

int [] arr = { 10, 20, 30, 40, 1, 2 };

int n = arr.Length;

int X = 91;

findFourElements(arr, n, X);

}

Javascript

<script>

function findFourElements(arr,n,X)

{

let mp = new Map();

for (let i = 0; i < n - 1; i++)

for (let j = i + 1; j < n; j++)

mp.set(arr[i] + arr[j], [i, j]);

for (let i = 0; i < n - 1; i++) {

for (let j = i + 1; j < n; j++) {

let sum = arr[i] + arr[j];

if (mp.has(X - sum)) {

let p = mp.get(X - sum);

if (p[0] != i && p[0] != j

&& p[1] != i && p[1] != j) {

document.write(

arr[i] + ", " + arr[j] + ", "

+ arr[p[0]] + ", "

+ arr[p[1]]);

return ;

}

let arr=[ 10, 20, 30, 40, 1, 2];

let n = arr.length;

let X = 91;

findFourElements(arr, n, X);

</script>

Complexity Analysis:

Time complexity: O(n^2).
Nested traversal is needed to store all pairs in the hash Map.
Auxiliary Space: O(n^2).
All n*(n-1) pairs are stored in hash Map so the space required is O(n^2)
Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.

Method 3: Solution having no duplicate elements

Approach:

Store sums of all pairs in a hash table
Traverse through all pairs again and search for X – (current pair sum) in the hash table.
Consider a temp array that is initially stored with zeroes. It is changed to 1 when we get 4 elements that sum up to the required value.
If a pair is found with the required sum, then make sure that all elements are distinct array elements and check if the value in temp array is 0 so that duplicates are not considered.

Below is the implementation of the code:

C++

#include <bits/stdc++.h>

using namespace std;

void fourSum( int X, int arr[], map< int ,

pair< int , int >> Map, int N)

{

int temp[N];

for ( int i = 0; i < N; i++)

temp[i] = 0;

for ( int i = 0; i < N - 1; i++)

{

for ( int j = i + 1; j < N; j++)

{

int curr_sum = arr[i] + arr[j];

if (Map.find(X - curr_sum) != Map.end())

{

pair< int , int > p = Map[X - curr_sum];

if (p.first != i && p.second != i

&& p.first != j && p.second != j

&& temp[p.first] == 0

&& temp[p.second] == 0 && temp[i] == 0

&& temp[j] == 0)

{

cout << arr[i] << "," << arr[j] <<

"," << arr[p.first] << "," << arr[p.second];

temp[p.second] = 1;

temp[i] = 1;

temp[j] = 1;

break ;

}

map< int , pair< int , int >> twoSum( int nums[], int N)

{

map< int , pair< int , int >> Map;

for ( int i = 0; i < N - 1; i++)

{

for ( int j = i + 1; j < N; j++)

{

Map[nums[i] + nums[j]].first = i;

Map[nums[i] + nums[j]].second = j;

}

return Map;

}

int main()

{

int arr[] = { 10, 20, 30, 40, 1, 2 };

int n = sizeof (arr) / sizeof (arr[0]);

int X = 91;

map< int , pair< int , int >> Map = twoSum(arr, n);

fourSum(X, arr, Map, n);

return 0;

}

Java

import java.util.*;

class fourElementWithSum {

public static void fourSum( int X, int [] arr,

Map<Integer, pair> map)

{

int [] temp = new int [arr.length];

for ( int i = 0 ; i < temp.length; i++)

temp[i] = 0 ;

for ( int i = 0 ; i < arr.length - 1 ; i++) {

for ( int j = i + 1 ; j < arr.length; j++) {

int curr_sum = arr[i] + arr[j];

if (map.containsKey(X - curr_sum)) {

pair p = map.get(X - curr_sum);

if (p.first != i && p.sec != i

&& p.first != j && p.sec != j

&& temp[p.first] == 0

&& temp[p.sec] == 0 && temp[i] == 0

&& temp[j] == 0 ) {

System.out.printf(

"%d,%d,%d,%d" , arr[i], arr[j],

arr[p.first], arr[p.sec]);

temp[p.sec] = 1 ;

temp[i] = 1 ;

temp[j] = 1 ;

break ;

}

public static Map<Integer, pair> twoSum( int [] nums)

{

Map<Integer, pair> map = new HashMap<>();

for ( int i = 0 ; i < nums.length - 1 ; i++) {

for ( int j = i + 1 ; j < nums.length; j++) {

map.put(nums[i] + nums[j], new pair(i, j));

}

return map;

}

public static class pair {

int first, sec;

public pair( int first, int sec)

{

this .first = first;

this .sec = sec;

}

public static void main(String args[])

{

int [] arr = { 10 , 20 , 30 , 40 , 1 , 2 };

int n = arr.length;

int X = 91 ;

Map<Integer, pair> map = twoSum(arr);

fourSum(X, arr, map);

}

Python3

def fourSum(X, arr, Map , N):

temp = [ 0 for i in range (N)]

for i in range (N - 1 ):

for j in range (i + 1 , N):

curr_sum = arr[i] + arr[j]

if (X - curr_sum) in Map :

p = Map [X - curr_sum]

if (p[ 0 ] ! = i and p[ 1 ] ! = i and

p[ 0 ] ! = j and p[ 1 ] ! = j and

temp[p[ 0 ]] = = 0 and temp[p[ 1 ]] = = 0 and

temp[i] = = 0 and temp[j] = = 0 ):

print (arr[i], "," , arr[j], "," ,

arr[p[ 0 ]], "," , arr[p[ 1 ]],

sep = "")

temp[p[ 1 ]] = 1

temp[i] = 1

temp[j] = 1

break

def twoSum(nums, N):

Map = {}

for i in range (N - 1 ):

for j in range (i + 1 , N):

Map [nums[i] + nums[j]] = []

Map [nums[i] + nums[j]].append(i)

Map [nums[i] + nums[j]].append(j)

return Map

arr = [ 10 , 20 , 30 , 40 , 1 , 2 ]

n = len (arr)

X = 91

Map = twoSum(arr, n)

fourSum(X, arr, Map , n)

C#

using System;

using System.Collections.Generic;

class GFG

{

static void fourSum( int X, int [] arr, Dictionary< int ,

Tuple< int , int >> Map, int N)

{

int [] temp = new int [N];

for ( int i = 0; i < N; i++)

temp[i] = 0;

for ( int i = 0; i < N - 1; i++)

{

for ( int j = i + 1; j < N; j++)

{

int curr_sum = arr[i] + arr[j];

if (Map.ContainsKey(X - curr_sum))

{

Tuple< int , int > p = Map[X - curr_sum];

if (p.Item1 != i && p.Item2 != i

&& p.Item1 != j && p.Item2 != j

&& temp[p.Item1] == 0

&& temp[p.Item2] == 0 && temp[i] == 0

&& temp[j] == 0)

{

Console.Write(arr[i] + "," + arr[j] +

"," + arr[p.Item1] + "," +

arr[p.Item2]);

temp[p.Item2] = 1;

temp[i] = 1;

temp[j] = 1;

break ;

}

static Dictionary< int , Tuple< int , int >> twoSum( int [] nums, int N)

{

Dictionary< int , Tuple< int , int >> Map =

new Dictionary< int , Tuple< int , int >>();

for ( int i = 0; i < N - 1; i++)

{

for ( int j = i + 1; j < N; j++)

{

Map[nums[i] + nums[j]] = new Tuple< int , int >(i, j);

}

return Map;

}

static void Main()

{

int [] arr = { 10, 20, 30, 40, 1, 2 };

int n = arr.Length;

int X = 91;

Dictionary< int , Tuple< int , int >> Map = twoSum(arr, n);

fourSum(X, arr, Map, n);

}

Javascript

<script>

class pair

{

constructor(first, sec)

{

this .first = first;

this .sec = sec;

}

function fourSum(X, arr, map)

{

let temp = new Array(arr.length);

for (let i = 0; i < temp.length; i++)

temp[i] = 0;

for (let i = 0; i < arr.length - 1; i++) {

for (let j = i + 1; j < arr.length; j++) {

let curr_sum = arr[i] + arr[j];

if (map.has(X - curr_sum)) {

let p = map.get(X - curr_sum);

if (p.first != i && p.sec != i

&& p.first != j && p.sec != j

&& temp[p.first] == 0

&& temp[p.sec] == 0 && temp[i] == 0

&& temp[j] == 0) {

document.write( arr[i]+ "," +arr[j]+ "," +

arr[p.first]+ "," +arr[p.sec]);

temp[p.sec] = 1;

temp[i] = 1;

temp[j] = 1;

break ;

}

function twoSum(nums)

{

let map = new Map();

for (let i = 0; i < nums.length - 1; i++) {

for (let j = i + 1; j < nums.length; j++) {

map.set(nums[i] + nums[j], new pair(i, j));

}

return map;

}

let arr=[10, 20, 30, 40, 1, 2];

let n = arr.length;

let X = 91;

let map = twoSum(arr);

fourSum(X, arr, map);

</script>

Complexity Analysis:

Time complexity: O(n^2).
Nested traversal is needed to store all pairs in the hash Map.
Auxiliary Space: O(n^2).
All n*(n-1) pairs are stored in hash Map so the space required is O(n^2) and the temp array takes O(n) so space comes to O(n^2).

Given a Set of Numbers Find Solution

Source: https://www.geeksforgeeks.org/find-four-elements-that-sum-to-a-given-value-set-2/

Knipe Stors1960

Given a Set of Numbers Find Solution

C++

C

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Menu Halaman Statis