Beginner

# 12. Efficient Methods to Find Pairs with Sum K in an Array

Objective: Write an algorithm to find out whether in a given array there exists or not two numbers whose sum is exactly equals to a given number.

```Input: An array arrA[], A number k
Output: True or false based upon we have found any two numbers in array arrA[] whose sum is equal to k```
Example:
```Input array: [1, 2, 3, 4, 5, 16, 17, 18, 19, 249]
k = 269
Output: false

k= 8
Output:
true
```

Approach:

Using Binary Search

• First sort the array
• Now do the linear scan to the from the left array , say starting index i=0
• Calculate RemSum = number - arrA[i]
• If RemSum<0, move to the next index
• If RemSum>0, Perform Binary Search for Rem_Sum on the remaining elements on the right side.

Time Complexity - O(nlogn)

Output

```[1, 2, 3, 4, 5, 16, 17, 18, 19, 249]
k= 269 - false
k= 8 - true
```

Method 2: Using Both Ends

1. Sort the array arrA
2. Have two pointer, i and j
3. I and j points to the first and last elements in the array, respectively.
4. Do Sum = arrA[i] + arrA[j]
5. If Sum > k , do j-- (move left).
6. If Sum < k, do i++ (move right)
7. If if Sum=k, return true.
8. Repeat steps from 4 to 7, while i<j

Output

Output

```[1, 2, 3, 4, 5, 16, 17, 18, 19, 249]
k= 269 - false
k= 8 - true
```