Given an array Arr[] of size L and a number N, you need to write a program to find if there exists a pair of elements in the array whose difference is N.
Example 1:
Input:
L = 6, N = 78
arr[] = {5, 20, 3, 2, 5, 80}
Output: 1
Explanation: (2, 80) have difference of 78.
Example 2:
Input:
L = 5, N = 45
arr[] = {90, 70, 20, 80, 50}
Output: -1
Explanation: There is no pair with difference of 45.
Your Task:
You need not take input or print anything. Your task is to complete the function findPair() which takes array arr, size of the array L and N as input parameters and returns True if required pair exists, else return False. 
Expected Time Complexity: O(L* Log(L)).
Expected Auxiliary Space: O(1).
Constraints:
1<=L<=10^{4 }
1<=Arr[i]<=10^{5 }
0<=N<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3



class Solution:



    def findPair(self, arr, L,N):

        #code here

Solutions:
class Solution:

	def findPair(self, arr, L, N):
		s = set()
		s.add(arr[0])
		for i in range(1, len(arr)):
			if arr[i] - N in s or arr[i] + N in s:
				return True
			else:
				s.add(arr[i])
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr = sorted(arr)
		for i in range(L):
			n = N + arr[i]
			if n in arr[i + 1:]:
				return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		i = 0
		j = 1
		while i < L and j < L:
			if i != j and arr[j] - arr[i] == N:
				return True
			elif arr[j] - arr[i] < N:
				j += 1
			else:
				i += 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		left = 0
		right = 1
		while left < L and right < L:
			diff = arr[right] - arr[left]
			if diff == N:
				return True
			elif diff < N:
				right += 1
			else:
				left += 1
				if left == right:
					right += 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		for i in range(L):
			num = N + arr[i]
			if num in arr[i + 1:]:
				return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		b = [] + arr
		for i in arr:
			b.remove(i)
			if N + i in b:
				return True
			b.append(i)
		return False


class Solution:

	def findPair(self, arr, L, N):
		if N == 0 and len(set(arr)) == len(arr):
			return 0
		elif N == 0:
			return 1
		for i in arr:
			if abs(N - i) in arr:
				return 1
		return 0


class Solution:

	def findPair(self, arr, L, N):
		s = 0
		arr.sort(reverse=True)
		if N == 0:
			arr = set(arr)
			if len(arr) == L:
				return False
			else:
				return True
		for i in range(0, L):
			s = arr[i] - N
			if s in arr:
				return True
				break
		if i == L - 1:
			return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		for i in reversed(range(L)):
			if arr[i] < N:
				break
			if arr[i] - N in arr:
				s = arr[i] - N
				if arr.index(s) != i:
					return 1
		return 0


from collections import Counter

class Solution:

	def findPair(self, arr, L, N):
		hmap = Counter(arr)
		if len(hmap) == L and N == 0:
			return False
		for (k, v) in hmap.items():
			if N + k in hmap:
				return True
		return False


class Solution:

	def findPair(self, a, L, N):
		a.sort()
		for i in range(L):
			(l, r) = (i, L)
			while r - l > 1:
				mid = (l + r) // 2
				if a[mid] < a[i] + N:
					l = mid
				else:
					r = mid
			if r != L and a[i] + N == a[r]:
				return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		count = 0
		a = set()
		for i in arr:
			d1 = i - N
			d2 = i + N
			if d1 in a or d2 in a:
				count += 1
			a.add(i)
		return count


class Solution:

	def findPair(self, arr, L, N):
		count = 0
		a = set()
		for i in arr:
			diff_1 = i - N
			diff_2 = i + N
			if diff_1 in a or diff_2 in a:
				count += 1
			a.add(i)
		return count


class Solution:

	def findPair(self, arr, L, N):
		elements = {}
		arr.sort()
		for i in arr:
			if abs(N - i) not in elements:
				if i not in elements:
					elements[i] = 1
				else:
					elements[i] += 1
			else:
				return True
		else:
			return False


class Solution:

	def findPair(self, arr, L, N):
		if N == 0:
			aset = set()
			for ele in arr:
				if ele in aset:
					return 1
				else:
					aset.add(ele)
			return 0
		aset = set(arr)
		for ele in aset:
			if ele + N in aset or ele - N in aset:
				return 1
		return 0


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		for i in range(len(arr)):
			l = i + 1
			r = len(arr) - 1
			while l <= r:
				mid = (l + r) // 2
				if arr[mid] == arr[i] + N:
					return 1
				elif arr[mid] > arr[i] + N:
					r = mid - 1
				else:
					l = mid + 1
		return 0


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		memo = {}
		for i in range(len(arr)):
			if memo.get(arr[i] - N):
				return 1
			else:
				memo[arr[i]] = 1
		return 0


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		i = 0
		j = L - 1
		while i < L - 1:
			x = arr[i] + N
			if x in arr[i + 1:]:
				return True
			i += 1
		return False


import collections
from collections import defaultdict

class Solution:

	def findPair(self, arr, L, N):
		arr.sort()

		def bs(i, arr, target, n):
			s = 0
			e = n - 1
			m = (s + e) // 2
			while s <= e:
				if arr[m] == target and m != i:
					return 1
				elif arr[m] > target:
					e = m - 1
				else:
					s = m + 1
				m = (s + e) // 2
			return 0
		ans = -1
		for i in range(L):
			a = arr[i]
			t = N + a
			ans = bs(i, arr, t, L)
			if ans == 1:
				break
		return ans


class Solution:

	def binarySearch(self, arr, high, low, key):
		while low <= high:
			mid = low + (high - low) // 2
			if arr[mid] == key:
				return key
			elif arr[mid] < key:
				low = mid + 1
			else:
				high = mid - 1
		return -1

	def findPair(self, arr, L, N):
		arr.sort()
		for i in range(L - 1):
			ans = self.binarySearch(arr, L - 1, i + 1, arr[i] + N)
			if ans != -1:
				return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		for i in range(L):
			if arr[i] + N in arr and arr.index(N + arr[i]) != i:
				return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		s = 0
		while s < L:
			if N + arr[s] in arr and arr.index(N + arr[s]) != s:
				return True
			s += 1
		return False


class Solution:

	def p_search(self, arr, L):
		for i in range(L - 1):
			if arr[i] == arr[i + 1]:
				return 1
		return 0

	def binarysearch(self, arr, L, N, k):
		left = 0
		right = L - 1
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] == k:
				return 1
			elif arr[mid] > k:
				right = mid - 1
			else:
				left = mid + 1
		return 0

	def findPair(self, arr, L, N):
		arr.sort()
		if N == 0:
			if self.p_search(arr, L):
				return True
			return False
		else:
			for i in range(L):
				if self.binarysearch(arr, L, N, arr[i] - N):
					return True
			return False


class Solution:

	def findPair(self, arr, L, N):
		a = False
		if N == 0:
			if L != len(set(arr)):
				a = True
			else:
				a = False
		elif N != 0:
			for i in arr:
				if N + i in arr:
					a = True
					break
		return a


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		l = 0
		r = 1
		while l < L and r < L:
			if arr[r] - arr[l] == N and l != r:
				return True
			elif arr[r] - arr[l] < N:
				r += 1
			else:
				l += 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		if L == len(set(arr)) and N == 0:
			return 0
		else:
			for i in range(L):
				if N + arr[i] in arr:
					return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, N) = [int(x) for x in input().split()]
		arr = [int(x) for x in input().split()]
		solObj = Solution()
		if solObj.findPair(arr, L, N):
			print(1)
		else:
			print(-1)


class Solution:

	def findPair(self, arr, L, N):
		output = False
		arr.sort()
		for i in range(L - 1):
			if N + arr[i] in arr[i + 1:]:
				return not output
		return output


class Solution:

	def findPair(self, arr, L, N):
		output = False
		if N == 0:
			if arr[2] != 2:
				return output
			else:
				return not output
		for i in arr:
			if abs(N + i) in arr:
				return not output
		return output


class Solution:

	def findPair(self, arr, L, N):
		mp = {}
		for i in arr:
			if i not in mp:
				mp[i] = 1
			else:
				mp[i] += 1
		for i in arr:
			if abs(i - N) in mp:
				if abs(i - N) == i and mp[abs(i - N)] > 1:
					return True
				elif abs(i - N) != i:
					return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		if N == 0 and len(arr) == len(set(arr)):
			return False
		for i in range(len(arr)):
			target = N + arr[i]
			if target in arr:
				return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		if N == 0:
			l = []
			for i in range(L):
				if arr[i] in l:
					return True
				l.append(arr[i])
			else:
				return False
		for i in range(L):
			if arr[i] + N in arr:
				return True
		else:
			return False


class Solution:

	def findPair(self, arr, L, N):
		d = {}
		for ele in arr:
			if abs(N - ele) in d or abs(N + ele) in d:
				return True
			else:
				d[ele] = 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		if N == 0 and L == len(set(arr)):
			return 0
		flag = 0
		i = 0
		j = i + 1
		while i < len(arr) and j < len(arr):
			if arr[j] - arr[i] == N:
				return 1
			elif arr[j] - arr[i] > N:
				i += 1
			else:
				j += 1
		return 0


class Solution:

	def findPair(self, arr, L, n):
		mpp = {}
		size = len(arr)
		for i in range(size):
			if arr[i] in mpp.keys():
				mpp[arr[i]] += 1
				if n == 0 and mpp[arr[i]] > 1:
					return True
			else:
				mpp[arr[i]] = 1
		if n == 0:
			return False
		for i in range(size):
			if n + arr[i] in mpp.keys():
				return True
		return False


class Solution:

	def findPair(self, array, L, N):
		freq = {}
		for item in array:
			freq[item] = 1 + freq.get(item, 0)
		if N == 0:
			for (key, value) in freq.items():
				if value > 1:
					return True
		else:
			for (key, _) in freq.items():
				if abs(N - key) in freq:
					return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		for i in range(L):
			start = i + 1
			end = L - 1
			while start <= end:
				mid = int((start + end) / 2)
				if arr[i] + N == arr[mid]:
					return 1
					break
				elif arr[mid] > arr[i] + N:
					end = mid - 1
				else:
					start = mid + 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		if N == 0:
			for i in range(len(arr) - 1):
				if arr[i] == arr[i + 1]:
					return True
			else:
				return False
		sorted(arr)
		for i in range(len(arr)):
			if arr[i] + N in arr:
				return True
		return False


class Solution:

	def findPair(self, arr, n, k):
		arr.sort()
		l = 0
		r = 1
		while l <= r and r < n:
			diff = arr[r] - arr[l]
			if diff == k and l != r:
				return True
			elif diff > k:
				l += 1
			else:
				r += 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		uniques = set(arr)
		if L == len(uniques) and N == 0:
			return False
		for num in arr:
			if N + num in uniques:
				return True
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		for i in range(L):
			left = i + 1
			right = L - 1
			while left <= right:
				mid = (left + right) // 2
				if arr[mid] - arr[i] == N:
					return True
				elif arr[mid] - arr[i] < N:
					left = mid + 1
				elif arr[mid] - arr[i] > N:
					right = mid - 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr = sorted(arr)
		i = 0
		j = 0
		while i < L and j < L:
			if i != j and abs(arr[i] - arr[j]) == N:
				return True
			if abs(arr[j] - arr[i]) <= N:
				j += 1
			else:
				i += 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		low = 0
		high = 1
		while low < L - 1 and high < L:
			if low != high:
				if arr[high] - arr[low] == N:
					return True
				elif arr[high] - arr[low] < N:
					high += 1
				elif arr[high] - arr[low] > N:
					low += 1
			else:
				high += 1
		return False


class Solution:

	def findPair(self, arr, L, N):
		c = 0
		m = 0
		a = set(arr)
		for i in arr:
			tc = N + i
			if tc in arr:
				if arr.count(tc) >= 2 and N == 0:
					m = m + 1
					break
				if arr.index(i) != arr.index(tc):
					c = c + 1
					break
		if c > 0 or m > 0:
			print(1)
		else:
			print(-1)


class Solution:

	def findPair(self, arr, L, N):
		arr.sort()
		s = {}
		l = 0
		for i in arr:
			s[i] = s.get(i, 0) + 1
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] > N:
				m = arr[i] - N
			else:
				m = N - arr[i]
			if m == arr[i]:
				if s[m] > 1:
					l = l + s[m]
					s[m] = 0
			elif m in s:
				l = l + s[m] * s[arr[i]]
				s[m] = 0
				s[arr[i]] = 0
		return l