Solved Problem - Triplet Sum

Problem statement

Given a sorted array of $N$ integers $A[]$. Find if there exists a triplet of integers $A[i]$, $A[j]$ and $A[k]$ such that the sum is equal to 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 three space-separated integers $i$, $j$ and $k$ such that $A[i] + A[j] + A[k] = X$ or print $-1$ if there is no such triplet.

---

Sample

Input

6 35
2 4 7 10 15 16

Output

2 5 6

---

Explanation

$2^{nd}$, $5^{th}$ and $6^{th}$ element of $A[]$ add upto $35$.

$A[2] = 4$

$A[5] = 15$

$A[6] = 16$

---

Brute force

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

---

Optimize to $O(N^{2})$

The algorithm is a slight modification of the Pair sum problem discussed earlier. If we iterate over the array for $i$ then we need to find a pair in the array $A[i+1...N]$ that adds to $X-A[i]$.

The second part is exactly the previous problem.