# two sum in array

Given an array of positive integers and an integer. Determine whether or not there exist two elements in A whose sum is exactly equal to that integer.

Example 1:

```
Input:
N = 6, X = 16
A[] = {1,4,45,6,10,8}
Output: Yes
Explanation: 10 and 6 are numbers
making a pair whose sum is equal to 16.
```

Example 2:

```
Input:
N = 5, X = 10
A[] = {1,2,4,3,6}
Output: Yes
```

**method 1 :**

The idea is to traverse input array and store array elements in a hash map if they are not in the map. else find the difference between x and the array element and if this result exist in map return true.

**c++ implementation:**

bool keypair(vector<int> a, int n, int x) { map<int,int>m; for(int i=0;i<n;i++) { if( m.find(x-a[i])!=m.end() ) return 1; else m[a[i]]++; } return 0; }

**Time Complexity:**O(n)

**space Complexity:**O(n)

**method 2 :**

- Sort the array
- Initialize l = 0 Initialize r = N-1
- Loop while l < r.
- If (A[l] + A[r] == x) then return 1
- Else if( A[l] + A[r] < x ) then l++
- Else r–

**c++ implementation:**

bool keypair(vector<int> A, int N, int x) { int l, r; sort(A.begin(), A.end()); l = 0; r = N - 1; while (l < r) { if (A[l] + A[r] == x) return 1; else if (A[l] + A[r] < x) l++; else // A[i] + A[j] > x r--; } return 0; }

**Time Complexity:**O(nlogn)

**space Complexity:**O(1)