Solved Problem  Pair Sum
We'll cover the following
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 spaceseparated integers $N(1 \leq N \leq 10^{5})$ and $X(1 \leq X \leq 10^{6})$.
The next line contains $N$ spaceseparated integers representing the array $A[](1 \leq A[i] \leq 10^{5})$.
Output format
Print a single line of two spaceseparated 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 $q1$. This will decrese the sum of $A[p] + A[q]$.
Get handson with 1200+ tech skills courses.