# Find four elements that sum to a given value | Set 3 (Hashmap)

Given an array of integers, Check if there exist four elements at different indexes in the array whose sum is equal to a given value k.
For example, if the given array is {1 5 1 0 6 0} and k = 7, then your function should print “YES” as (1+5+1+0=7).

Examples:

```Input  : arr[] = {1 5 1 0 6 0}
k = 7
Output : YES

Input :  arr[] = {38 7 44 42 28 16 10 37
33 2 38 29 26 8 25}
k = 22
Output : NO
```

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

We have discussed different solutions in below two sets.
Find four elements that sum to a given value | Set 1 (n^3 solution)
Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution)

In this post, an optimized solution is discussed that works in O(n2) on average.

The idea is to create a hashmap to store pair sums.

```Loop i = 0 to n-1 :
Loop j = i + 1 to n-1
calculate sum = arr[i] + arr[j]
If (k-sum) exist in hash
a) Check in hash table for all
pairs of indexes which form
(k-sum).
b) If there is any pair with no
no common indexes.
return true
Else  update hash table
EndLoop;
EndLoop;
```

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

 `// C++ program to find if there exist 4 elements ` `// with given sum ` `#include ` `using` `namespace` `std; ` ` `  `// function to check if there exist four ` `// elements whose sum is equal to k ` `bool` `findfour(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// map to store sum and indexes for ` `    ``// a pair sum ` `    ``unordered_map<``int``, vector > > hash; ` ` `  `    ``for` `(``int` `i = 0; i < n; i++) { ` `        ``for` `(``int` `j = i + 1; j < n; j++) { ` ` `  `            ``// calculate the sum of each pair ` `            ``int` `sum = arr[i] + arr[j]; ` ` `  `            ``// if k-sum exist in map ` `            ``if` `(hash.find(k - sum) != hash.end()) { ` `                ``auto` `num = hash.find(k - sum); ` `                ``vector > v = num->second; ` ` `  `                ``// check for index coincidence as if ` `                ``// there is a common that means all ` `                ``// the four numbers are not from ` `                ``// different indexes and one of the ` `                ``// index is repeated ` `                ``for` `(``int` `k = 0; k < num->second.size(); k++) { ` ` `  `                    ``pair<``int``, ``int``> it = v[k]; ` ` `  `                    ``// if all indexes are different then ` `                    ``// it means four number exist ` `                    ``// set the flag and break the loop ` `                    ``if` `(it.first != i && it.first != j &&  ` `                        ``it.second != i && it.second != j) ` `                        ``return` `true``; ` `                ``} ` `            ``} ` ` `  `            ``// store the sum and index pair in hashmap ` `            ``hash[sum].push_back(make_pair(i, j)); ` `        ``} ` `    ``} ` `    ``hash.clear(); ` `    ``return` `false``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `k = 7; ` `    ``int` `arr[] = { 1, 5, 1, 0, 6, 0 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``if` `(findfour(arr, n, k)) ` `        ``cout ` `            ``<< ``"YES"` `<< endl; ` `    ``else` `        ``cout << ``"NO"` `<< endl; ` `    ``return` `0; ` `} `

Output:

```YES
```

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

## tags:

Arrays Hash Arrays Hash