-1
$\begingroup$

I am currently stuck on this problem, it is from a very highly competitive contest and so it is highly difficult as well. Below is the statement:

There are 2 lists of integers with the same length. 
Pick an integer from each list and
calculate the absolute value of their sum. 
Return the minimum value for the value.

Example: list1 = [1, 2]; list2 = [-2, 3] => result = 0

Explanation : take 2 and -2

Can anyone help?

Problem Source: 2008 Vietnamese National Student Competition ("Kì thi học sinh giỏi quốc gia"), question 1

I know that there is a brute force solution, but I got Time Limit Exceed (TLE), which means this MUST be done with less than $O(n^2)$ time complexity.

Improve this question
$\endgroup$
3
  • $\begingroup$ Both Lists are already sorted or not? $\endgroup$
    – user19121278
    Jun 23 at 6:14
  • $\begingroup$ @user19121278 No. $\endgroup$
    – Minh Đức Hoàng
    Jun 23 at 7:15
  • 2
    $\begingroup$ Please edit the question to credit the source and include all relevant information in the question -- we ask that you don't put clarifications in the comments, but edit the question so it reads well for someone who encounters it for the first time and so people don't need to read the comments. $\endgroup$
    – D.W. ♦
    Jun 23 at 17:24

2 Answers 2

Reset to default
2
$\begingroup$

An $O(n\log n)$ solution:

Sort the second list. For every element of the first, let $e$, find the two elements just smaller and just larger than $-e$, by dichotomic search. Then keep the smallest absolute sum. It is possible that one of the two elements does not exist.

E.g. $-7,-3,4, 6$ vs. $-2,-1,4,9$.

$\begin{align}-7&\to4<7<9&\to2\\-3&\to-1<3<4&\to1\\4&\to.<-4<-2&\to2\\6&\to .<-6<-2&\to4\end{align}$

Improve this answer
$\endgroup$
3
  • $\begingroup$ It is not impossible that an $O(n)$ solution exists, based on the "two-pointers" method. $\endgroup$
    – Yves Daoust
    Jun 23 at 12:20
  • $\begingroup$ I would bet on it is impossible (without further information). I would bet so will you bet. $\endgroup$
    – John L.
    Jun 23 at 21:17
  • $\begingroup$ @JohnL.: ooops, I silently assumed the two lists sorted for an $O(n)$ solution. $\endgroup$
    – Yves Daoust
    Jun 24 at 6:03
-1
$\begingroup$

A solution that will often take not much more than n operations (but no guarantee):

  1. In constant time find the range of both arrays, like -7 .. 6 and -2 .. 9 in the example.
  2. Calculate the number of sums (16 in this case).
  3. Make a guess for the smallest absolute difference say 2 in this case.
  4. Create a hash table that lets you look up x div 2 (in this example) quickly, fill it with items from the second array.

Now look up the values from the first array. Say the first array had a value of -7, so you look up 2, 3 and 4 in the hash table. This would find values from 4 to 9, with an absolute value of the sum from 0 to 3. There’s a good chance to find the solution in linear time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.