Solved Problem - Pair Sum

Problem statement

Given a sorted array of $N$ integers $A[]$. Find if there exist a pair of integers $A[i]$ and $A[j]$ such that the sum is equal to the given integer $X$.

Input format

The first line of input consists of two space-separated integers $N(1 \leq N \leq 10^{5})$ and $X(1 \leq X \leq 10^{6})$.

The next line contains $N$ space-separated integers representing the array $A[](1 \leq A[i] \leq 10^{5})$.

Output format

Print a single line of two space-separated integers $i$ and $j$ such that $A[i] + A[j] = X$ or print $-1$ if there is no such pair.

---

Sample

Input

6 14
2 4 7 10 15 16

Output

2 4

---

Explanation

$2^{nd}$ and $4^{th}$ element of $A[]$ add upto $14$.

$A[2] = 4$

$A[4] = 10$

---

Brute force

Use two loops to iterate over the array and check all ${N} \choose {2}$ pairs. Time complexity is $O(N^{2})$.

---

Optimization to $O(N)$

Let’s see how we can optimize the time, even more, using $2$ pointers. The algorithm is very similar to binary search in terms of how we move the pointers.

We start from the two ends of the sorted array using two pointers lets call the $p$ and $q$. The algorithm:

Compare $A[p] + A[q]$ and $X$:

• If X is equal, we found a pair $A[p],A[q]$.

• If X is greater, move $p$ to $p+1$. This will increase the sum of $A[p] + A[q]$.

• If X is smaller, move $q$ to $q-1$. This will decrese the sum of $A[p] + A[q]$.