Quadruple Sum Nearest a Target
You are given four lists, each of n numbers, and a target. Pick one number from each list and print the smallest possible gap between their sum and the target. The gap is reported as a non-negative amount, so a sum above the target counts the same as one the same distance below.
You must pick from every list, so the number of picked values is always exactly four.
## What most people try first
Four nested loops, n^4, hopeless at n = 1000.
The subtler wrong turn is to look only below the target, in the style of a capacity problem. That answers a different question. The target here can perfectly well sit above everything reachable or below everything reachable, and in general the nearest sum is as often above it as below.
## Split the quadruple
Build the sorted list of every a + b from the first two lists. For each c + d from the last two, the ideal partner is target minus c minus d, so binary search the sorted list for that value and examine the entry at the insertion point and the entry just before it.
## Why two entries suffice
The list is sorted, so every entry from the insertion point onward is at least the wanted value and every entry before it is below. The nearest candidate above is therefore the one AT the insertion point and the nearest below is the one immediately before. Anything further out in either direction is strictly further from the wanted value, so no third candidate can beat them.
## Why deduplicating the first half is safe here, unlike in the counting version
The question asks only how close you can get, so two different position pairs that produce the same sum are interchangeable. Storing the distinct sums is therefore correct and smaller. Contrast that with the counting version of this question, where collapsing equal sums is a wrong answer rather than a saving. The structure follows from what is being asked, which is the recurring lesson of this block.
## The boundary that breaks a careless implementation
The insertion point can be 0, where nothing lies below, and it can equal the length, where nothing lies at or above. Both ends must be guarded. The tests include a target below everything reachable and a target above everything reachable so that each end is exercised.
The answer must also be seeded from an actual candidate rather than from 0, since 0 would be reported as the answer on every input.
## Overflow
Values reach 10^9 in magnitude, so a half-sum reaches 2 * 10^9 and the full sum 4 * 10^9. The value searched for, target minus c minus d, can be negative, so the type must be signed as well as 64 bits. In C an unsigned type here wraps to an enormous positive value and the search lands at the far end of the array.
## Cost
n^2 to build and sort the first half, n^2 binary searches. A few million steps at n = 1000.
## Worked example
``` A = 1 2 B = 1 2 C = 1 2 D = 1 2 target 7
distinct sums of A and B, sorted: 2 3 4
c + d = 2 want 5 insertion point 3, nothing at it; below is 4 -> sum 6, gap 1 c + d = 3 want 4 entry 4 is there -> sum 7, gap 0 c + d = 4 want 3 entry 3 is there -> sum 7, gap 0
answer 0 ```
### Constraints - 1 <= n <= 1000 - each number is between -10^9 and 10^9 - the target is between -4 * 10^9 and 4 * 10^9 - Sums reach 4 * 10^9 in magnitude and the value searched for can be negative, so a signed 64-bit type is required.