Problem statement

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

Input format

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

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

Output format

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



6 14
2 4 7 10 15 16


2 4


2nd2^{nd} and 4th4^{th} element of A[]A[] add upto 1414.

A[2]=4A[2] = 4

A[4]=10A[4] = 10

Brute force

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

Optimization to O(N)O(N)

Let’s see how we can optimize the time, even more, using 22 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 pp and qq. The algorithm:

Compare A[p]+A[q]A[p] + A[q] and XX:

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

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

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

Get hands-on with 1200+ tech skills courses.