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 :

  1. Sort the array
  2. Initialize l = 0 Initialize  r = N-1
  3. Loop while l < r. 
    1. If (A[l] + A[r] == x) then return 1
    2. Else if( A[l] + A[r] < x ) then l++
    3. 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) 
darkmode