Part 4 of 22 in Binary Search  

Find all pairs with sum K by animeshn

Problem statement

Given a sorted list of integers with no duplicates, find all distinct pair of integers in the list with sum equal to a given number K in O (n*logn ) or O(n) time complexity.

Input

First line of input will contain a positive integer T = number of test cases. Each test case will contain 2 lines. First line of each test case two positive integer - N and K. Next line will contain N unique numbers separated by space in increasing order.

Output

For each test case, print number of distinct pairs whose sum will be equal to k. A pair must have two numbers at different indices. Two pairs are different if at least one of the indices in them is uncommon. Indices - (2,3) and (3,2) are not distinct, but (2,3) and (2,4) are.

Sample Input
3
10 11
1 2 3 4 5 6 7 8 9 10
5 10
2 4 6 8 10
6 27
12 15 20 22 34 36

Sample Output
5
2
1


1) O(nlogn) approach -The list is sorted. Do you think binary search can help?

2) O(n) approach -Start with two pointers at start and end of list. Move both if sum is K. Move one of them for other scenarios. 


To try out your code



Sign in

Sign up