This post is completed by 1 user

  • 0
 Add to List
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

Related Problems: