Given two sorted arrays and a number x, find the pair whose sum is closest to x and the pair has an element from each array. In the case of multiple closest pairs return any one of them.
Note: The output represents the closest difference of the sum with the number x.
Example 1:
Input : arr[ ] = {1, 4, 5, 7}
brr[ ] = {10, 20, 30, 40} 
X = 32
Output : 1
Explanation:
The closest pair whose sum is closest
to 32 is {1, 30} = 31.
Example 2:
Input : arr[ ] = {1, 4, 5, 7}
brr[ ] = {10, 20, 30, 40}
X = 50 
Output :  3 
Explanation: 
The closest pair whose sum is closest
to 50 is {7, 40} = 47.
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function printClosest() that takes an array (arr), another array (brr), size of array arr (N), size of array brr (M), and return the array of two integers whose sum is closest to X. The driver code takes care of the printing of the closest difference.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N, M ≤ 10^{5}
1 ≤ A[i], B[i] ≤ 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def printClosest (self,arr, brr, n, m, x) : 

        #code here

Solutions:
class Solution:

	def printClosest(self, arr, brr, n, m, x):
		l = 0
		s = m - 1
		diff = 2 ** 31 - 1
		res = []
		while l < n and s >= 0:
			if abs(arr[l] + brr[s] - x) < diff:
				diff = abs(arr[l] + brr[s] - x)
				res = [arr[l], brr[s]]
			if arr[l] + brr[s] > x:
				s -= 1
			else:
				l += 1
		return res


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		if arr[0] > brr[0]:
			l = 0
			r = n - 1
			(arr, brr) = (brr, arr)
			ans = [brr[0], arr[-1]]
		else:
			l = 0
			r = m - 1
			ans = [arr[0], brr[-1]]
		while l < len(arr) and r >= 0:
			if abs(x - arr[l] - brr[r]) < abs(x - ans[0] - ans[1]):
				ans = [arr[l], brr[r]]
			if arr[l] + brr[r] > x:
				r -= 1
			elif arr[l] + brr[r] < x:
				l += 1
			else:
				break
		return ans


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		differ = float('inf')
		l = 0
		r = m - 1
		result = [1, 1]
		while l < n and r >= 0:
			if abs(arr[l] + brr[r] - x) < differ:
				differ = abs(arr[l] + brr[r] - x)
				result[0] = arr[l]
				result[1] = brr[r]
			if arr[l] + brr[r] < x:
				l += 1
			else:
				r -= 1
		return result


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		j = m - 1
		i = 0
		diff = 2 ** 31
		result = [0, 0]
		while i < len(arr) and j >= 0:
			sum = arr[i] + brr[j]
			if diff > abs(sum - x):
				diff = abs(sum - x)
				result[0] = arr[i]
				result[1] = brr[j]
			if sum >= x:
				j = j - 1
			else:
				i = i + 1
		return result


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		closestSum = 200001
		(i, j) = (0, m - 1)
		res = [100000, 100000]
		while i < n and j >= 0:
			curSum = arr[i] + brr[j]
			if abs(curSum - x) < abs(closestSum - x):
				res[0] = arr[i]
				res[1] = brr[j]
				closestSum = curSum
			if curSum < x:
				i += 1
			elif curSum > x:
				j -= 1
			else:
				return [arr[i], brr[j]]
		return res


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = 0
		j = len(brr) - 1
		ans = float('inf')
		while i < len(arr) and j >= 0:
			if ans > abs(arr[i] + brr[j] - x):
				l_i = i
				r_j = j
				ans = abs(arr[i] + brr[j] - x)
			if arr[i] + brr[j] > x:
				j -= 1
			else:
				i += 1
		return [arr[l_i], brr[r_j]]


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		arr.reverse()
		pair = [0, 0]
		diff = float('inf')
		while arr and brr:
			summa = arr[-1] + brr[-1] - x
			if abs(summa) < diff:
				diff = abs(summa)
				pair = [arr[-1], brr[-1]]
			if summa < 0:
				arr.pop()
			elif summa > 0:
				brr.pop()
			else:
				return pair
		return pair


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		res = [0, 0]
		minf = float('inf')
		(i, j) = (0, m - 1)
		while i < n and j >= 0:
			pair = arr[i] + brr[j]
			if abs(pair - x) < minf:
				minf = min(minf, abs(pair - x))
				res = [arr[i], brr[j]]
			if pair == x:
				break
			elif pair > x:
				j -= 1
			else:
				i += 1
		return res


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		l = 0
		r = m - 1
		res2 = 0
		diff = 1000000007
		res1 = 0
		while l < n and r >= 0:
			summ = arr[l] + brr[r]
			if abs(summ - x) < diff:
				diff = abs(summ - x)
				res1 = arr[l]
				res2 = brr[r]
			if summ < x:
				l += 1
			else:
				r -= 1
		return (res1, res2)


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		diff = float('inf')
		l = 0
		r = m - 1
		ans = list()
		while l < n and r >= 0:
			if abs(arr[l] + brr[r] - x) < diff:
				diff = abs(arr[l] + brr[r] - x)
				if len(ans) != 0:
					ans.pop()
					ans.pop()
				ans.append(arr[l])
				ans.append(brr[r])
			if arr[l] + brr[r] < x:
				l += 1
			else:
				r -= 1
		return ans


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		diff = 1000000000
		res_l = 0
		res_r = 0
		l = 0
		r = m - 1
		while l < n and r >= 0:
			if abs(arr[l] + brr[r] - x) < diff:
				res_l = l
				res_r = r
				diff = abs(arr[l] + brr[r] - x)
			if arr[l] + brr[r] > x:
				r = r - 1
			else:
				l = l + 1
		return [arr[res_l], brr[res_r]]


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		l = 0
		r = m - 1
		dif = 1000000000
		a = b = 0
		while l < n and r >= 0:
			if abs(arr[l] + brr[r] - x) < dif:
				dif = abs(arr[l] + brr[r] - x)
				a = arr[l]
				b = brr[r]
			elif arr[l] + brr[r] < x:
				l += 1
			else:
				r -= 1
		return (a, b)


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		min_diff = 9999999
		i = 0
		j = m - 1
		while i < n and j >= 0:
			diff = abs(arr[i] + brr[j] - x)
			if diff < min_diff:
				min_diff = diff
				l = [arr[i], brr[j]]
			elif arr[i] + brr[j] > x:
				j = j - 1
			else:
				i += 1
		return l


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		diff = 100000 ** 9
		l = 0
		r = m - 1
		ans = []
		while l < n and r >= 0:
			if abs(arr[l] + brr[r] - x) < diff:
				diff = abs(arr[l] + brr[r] - x)
				if len(ans) != 0:
					ans.pop()
					ans.pop()
				ans.append(arr[l])
				ans.append(brr[r])
			if arr[l] + brr[r] < x:
				l += 1
			else:
				r -= 1
		return ans


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		(i, j) = (0, m - 1)
		mn = 10 ** 9
		while i < n and j >= 0:
			s = arr[i] + brr[j]
			d = x - s
			if abs(d) < mn:
				mn = abs(d)
				res = [arr[i], brr[j]]
			if d < 0:
				j -= 1
			elif d > 0:
				i += 1
			else:
				return [arr[i], brr[j]]
		return res


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = 0
		j = m - 1
		d = 9999999999
		k = [-1, -1]
		while i < n and j >= 0:
			if abs(arr[i] + brr[j] - x) < d:
				d = abs(arr[i] + brr[j] - x)
				k[0] = arr[i]
				k[1] = brr[j]
			if arr[i] + brr[j] == x:
				return [arr[i], brr[j]]
			if arr[i] + brr[j] < x:
				i += 1
			else:
				j -= 1
		return k


import sys

class Solution:

	def printClosest(self, arr, brr, n, m, x):
		arr.sort()
		brr.sort()
		(i, j) = (0, m - 1)
		min_ = sys.maxsize
		while i < n and j >= 0:
			sum_ = arr[i] + brr[j]
			if abs(sum_ - x) < min_:
				a_min = arr[i]
				b_min = brr[j]
				min_ = abs(sum_ - x)
			elif sum_ > x:
				j -= 1
			else:
				i += 1
		return [a_min, b_min]


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = 0
		j = m - 1
		ans = float('inf')
		ans_tuple = None
		while i < n and j >= 0:
			diff = x - (arr[i] + brr[j])
			if abs(diff) < ans:
				ans = abs(diff)
				ans_tuple = (arr[i], brr[j])
			if diff <= 0:
				j -= 1
			else:
				i += 1
		return ans_tuple


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		min_diff = 12345678
		ans = [0, 0]
		low = 0
		high = m - 1
		while low < n and high >= 0:
			if abs(arr[low] + brr[high] - x) < min_diff:
				min_diff = abs(arr[low] + brr[high] - x)
				ans[0] = arr[low]
				ans[1] = brr[high]
			if arr[low] + brr[high] < x:
				low += 1
			else:
				high -= 1
		return ans


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = 0
		j = len(brr) - 1
		pair = [arr[i], brr[j]]
		mindiff = float('inf')
		while i < len(arr) and j >= 0:
			diff = abs(arr[i] + brr[j] - x)
			if diff < mindiff:
				mindiff = diff
				pair = [arr[i], brr[j]]
			if arr[i] + brr[j] < x:
				i += 1
			else:
				j -= 1
		return pair


import math

class Solution:

	def printClosest(self, arr, brr, n, m, x):
		diff = math.inf
		res_l = 0
		res_r = 0
		l = 0
		r = m - 1
		while l < n and r >= 0:
			if abs(arr[l] + brr[r] - x) < diff:
				res_l = l
				res_r = r
				diff = abs(arr[l] + brr[r] - x)
			if arr[l] + brr[r] > x:
				r = r - 1
			else:
				l = l + 1
		return [arr[res_l], brr[res_r]]
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	brr = list(map(int, input().strip().split()))
	x = int(input())
	ob = Solution()
	ans = ob.printClosest(arr, brr, n, m, x)
	print(abs(ans[0] + ans[1] - x))


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		low = 0
		high = m - 1
		minDiff = float('inf')
		while low < n and high > -1:
			if abs(arr[low] + brr[high] - x) < minDiff:
				minDiff = abs(arr[low] + brr[high] - x)
				pair = [arr[low], brr[high]]
				if minDiff == 0:
					return pair
			if arr[low] + brr[high] > x:
				high -= 1
			elif arr[low] + brr[high] < x:
				low += 1
		return pair


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		import sys
		diff = sys.maxsize
		l = 0
		r = m - 1
		ans = []
		while l < n and r >= 0:
			if abs(arr[l] + brr[r] - x) < diff:
				res_l = l
				res_r = r
				diff = abs(arr[l] + brr[r] - x)
			if arr[l] + brr[r] > x:
				r = r - 1
			else:
				l = l + 1
		ans.append(arr[res_l])
		ans.append(brr[res_r])
		return ans


import sys

class Solution:

	def printClosest(self, arr, brr, n, m, x):
		start = 0
		end = m - 1
		diff = sys.maxsize
		while start < n and end >= 0:
			if abs(arr[start] + brr[end] - x) < diff:
				diff = abs(arr[start] + brr[end] - x)
				start_ans = start
				end_ans = end
			if arr[start] + brr[end] > x:
				end -= 1
			else:
				start += 1
		return [arr[start_ans], brr[end_ans]]


from math import inf

class Solution:

	def printClosest(self, arr, brr, n, m, x):
		n = len(arr)
		m = len(brr)
		l = 0
		r = m - 1
		diff = inf
		while l < n and r >= 0:
			v = arr[l] + brr[r]
			if abs(v - x) < diff:
				diff = abs(v - x)
				ans = [arr[l], brr[r]]
			if v > x:
				r -= 1
			else:
				l += 1
		return ans


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		low = 0
		high = m - 1
		soFarMinDiff = float('inf')
		result = [-1, -1]
		while low < n and high >= 0:
			tmp = arr[low] + brr[high]
			diff = abs(tmp - x)
			if diff < soFarMinDiff:
				soFarMinDiff = diff
				result = [arr[low], brr[high]]
			if tmp == x:
				break
			elif tmp < x:
				if low + 1 < n:
					low += 1
				else:
					break
			elif high - 1 >= 0:
				high -= 1
			else:
				break
		return (result[0], result[1])


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = 0
		j = m - 1
		min1 = 999999
		ls = []
		while i < n and j >= 0:
			sum1 = arr[i] + brr[j]
			if abs(x - sum1) < min1:
				min1 = abs(x - sum1)
				if ls != []:
					ls[0] = arr[i]
					ls[1] = brr[j]
				else:
					ls.append(arr[i])
					ls.append(brr[j])
			if sum1 == x:
				break
			elif sum1 > x:
				j -= 1
			else:
				i += 1
		return ls


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = n - 1
		j = 0
		ad = arr[i] + brr[j]
		ai = aj = -1
		while i >= 0 and j < m:
			nd = arr[i] + brr[j]
			if abs(nd - x) <= abs(ad - x):
				ad = nd
				ai = i
				aj = j
			if nd < x:
				j += 1
			else:
				i -= 1
		return (arr[ai], brr[aj])


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = 0
		j = m - 1
		diff = 100000
		finali = 0
		finalj = m - 1
		while i <= n - 1 and j >= 0:
			temp = arr[i] + brr[j]
			temp2 = abs(temp - x)
			if temp2 < diff:
				diff = temp2
				finali = i
				finalj = j
			if temp < x:
				i += 1
			elif temp == x:
				return (arr[i], brr[j])
			else:
				j -= 1
		return (arr[finali], brr[finalj])


class Solution:

	def printClosest(self, arr, brr, n, m, k):
		arr.sort()
		brr.sort()
		a = 0
		b = m - 1
		ax = arr[0]
		bx = brr[m - 1]
		while a < n and b >= 0:
			if abs(arr[a] + brr[b] - k) < abs(ax + bx - k):
				ax = arr[a]
				bx = brr[b]
			if arr[a] + brr[b] > k:
				b -= 1
			else:
				a += 1
		return [ax, bx]


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		(l1, l2) = (0, len(brr) - 1)
		(v1, v2) = (0, 0)
		diff = float('inf')
		while l1 < n and l2 >= 0:
			comp = abs(arr[l1] + brr[l2] - x)
			if comp < diff:
				diff = comp
				v1 = l1
				v2 = l2
			if arr[l1] + brr[l2] < x:
				l1 += 1
			else:
				l2 -= 1
		return (arr[v1], brr[v2])


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		(lo, hi) = (0, m - 1)
		diff = 0
		minDiff = float('inf')
		result = []
		while lo < n and hi >= 0:
			diff = abs(arr[lo] + brr[hi] - x)
			if diff < minDiff:
				result = [arr[lo], brr[hi]]
				minDiff = diff
			if x > arr[lo] + brr[hi]:
				lo += 1
			else:
				hi -= 1
		return result


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		i = 0
		j = m - 1
		diff = 10000000000000
		t = [0, 0]
		while i < n and j >= 0:
			if abs(arr[i] + brr[j] - x) < diff:
				diff = abs(arr[i] + brr[j] - x)
				t = [arr[i], brr[j]]
			if arr[i] + brr[j] < x:
				i += 1
			else:
				j -= 1
		return t


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		(i, j) = (0, m - 1)
		diff = 10 ** 9
		while i < n and j >= 0:
			now = arr[i] + brr[j]
			if abs(now - x) < diff:
				diff = abs(now - x)
				ans = (arr[i], brr[j])
			if now <= x:
				i += 1
			else:
				j -= 1
		return ans


class Solution:

	def printClosest(self, arr, brr, n, m, x):
		diff = 100000000.0 * 2 + 1
		(a, b) = (None, None)
		(i, j) = (0, m - 1)
		while i < n and j >= 0:
			cur_diff = abs(x - arr[i] - brr[j])
			if cur_diff < diff:
				diff = cur_diff
				(a, b) = (arr[i], brr[j])
			if arr[i] + brr[j] > x:
				j -= 1
			else:
				i += 1
		return (a, b)