CODEWITHSUNDEEP
arraysalgorithm
Cong Tran An
Cong Tran An

Reputation: 135

Given two arrays with same size, find the couple of elements from both arrays that make sum with the smallest absolute value

I was tasked with this problem yesterday, and since then was trying to find a efficient solution for it.
The detail of the solution is: Given two arrays a[n], b[n], find a pair (a[i],b[j]) so that abs(a[i]+b[j]) is as small as possible. The two array consist of integer elements not greater than 1 billion, and n here is at most 10000.
I know that a solution consist of two for loops here is impractical since the arrays sizes are less or equal to 10000.
I am thinking of a solution where I will sort these elements in a manner, which I haven't found out yet, so that we can easily identified the sum which has the least absolute value, since my class is learning about sorting algorithms.
Can you help me figure out the manner here.
PS: Sorry, I can't type the mathematics symbols here.

Upvotes: 0

Views: 391

Answers (2)

asp
asp

Reputation: 172

You could negate one of the lists and sort this together with the other list. In this new list you look for two consecutive entries with the smallest distance and such that the two entries are one from each original list.

If a[i], i=0,1,...,n is the first and b[j], j=0,1,...,n is hthe second, then min(|a[k]+b[l]|)=min(|a[k]-(-b[l])|). So instead of minimizing the sum of a[k] and b[l] for some k,l we can minimize the difference between a[k] and -b[l] for some k,l. So we look for a pair a[k], -b[l] as close together as possible. Such a pair must be consecutive in a list obtained from sorting a[i], -b[j] for i,j=0,1,...,n into a single list c[t] of length 2n.

Sorting c is O(n log n), running through c is O(n), so the running time is dominated by sorting.

Upvotes: 0

User_Targaryen
User_Targaryen

Reputation: 4225

I have a Python code that solves the problem in O(nlogn + mlogm) + O(m+n) = O(nlogn + mlogm) time, where n is the length of the first array and m is the length of the second array. Here is the code:

arr1.sort()
arr2.sort(reverse = True)
n = len(arr1)
m = len(arr2)
print arr1
print arr2
minim = abs(arr1[0] + arr2[0])

i = 0
j = 0

while i<n and j<m:
   minimum = abs(arr1[i] + arr2[j])
   minim = min(minim,minimum)
   if arr1[i]>0 and arr2[j]>0:
      j += 1
   elif arr1[i]<=0 and arr2[j]<=0:
      i += 1
   elif arr1[i]>0 and arr2[j]<=0:
      if abs(arr1[i]) > abs(arr2[j]):
          j += 1
      else:
          i += 1
   elif arr1[i]<=0 and arr2[j]>0:
      if abs(arr1[i]) > abs(arr2[j]):
          i += 1
      else:
          j += 1

print minim

Example:

arr1[] = [-23, -10, 30, 44, 45]

arr2[] = [61, 55, 32, 22, -55]

Answer: 1

Upvotes: 1

Related Questions