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 36Sample 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.