2369. Total Nearest a Target

You are given n numbers and a target. Choose any collection of them, including none, and print the smallest possible gap between their total and the target. The gap is reported as a non-negative amount, so a total above the target counts the same as one the same distance below it.

The empty collection has total 0, so a gap of exactly the target is always achievable, and the answer is never larger than that.

## What most people try first

Walking every collection is 2^n, about 10^12 at n = 40.

The more interesting wrong turn is to reuse a capacity-style solution, searching only for the largest total that does not EXCEED the target. That answers a different question. If the numbers are 10, 20, 30 and the target is 5, the best total below the target is 0, a gap of 5, while the total 10 sits only 5 above it and ties; change the target to 7 and the total 10 is a gap of 3 while the best total below is a gap of 7. Searching one side of the target only is wrong about half the time.

A table indexed by the total cannot be built, because the numbers reach 10^9 so the totals reach 4 * 10^10.

## Halve the list

Split into halves of about twenty and enumerate the reachable totals of each. Sort the left totals.

For a fixed right total r, you want the left total nearest to target minus r. In a sorted array nearest means: binary search for the insertion point of that value, then compare the entry just below it and the entry at it. One of those two is the nearest, and there is no way to know which in advance, which is why both must be checked.

## Why checking two entries is enough

The sorted array is non-decreasing, so everything at or after the insertion point is at least the wanted value and everything before it is below. The closest element above is therefore the one AT the insertion point, and the closest below is the one immediately before it. Anything further away in either direction is further from the wanted value, so no third candidate can win.

## The boundary that breaks a careless implementation

The insertion point can be 0, meaning nothing is below, and it can be the length of the array, meaning nothing is at or above. Both cases must be guarded or the lookup runs off an end. The smallest inputs hit both: a single number smaller than the target reaches one end, and a target of 0 reaches the other.

The answer must also be seeded from a reachable total rather than from zero. Seeding at zero reports a gap of 0 on every input.

## Overflow

Totals reach 4 * 10^10 and the target does too, so the totals, the target and the gap all need 64 bits. Note that target minus r can be NEGATIVE, so the type must be signed, and in C an unsigned type here wraps to an enormous positive value and the binary search then lands at the far end of the array.

## Cost

2^(n/2) per half, one sort, and one binary search plus two comparisons per right total.

## Worked example

``` numbers 3 1 4 2 target 11 (total is 10, so 11 is unreachable)

left half 3 1 reachable totals 0 1 3 4 right half 4 2 reachable totals 0 2 4 6 left totals sorted 0 1 3 4

r = 0 want 11 insertion point 4 below: 4 -> gap |11 - 4| = 7 r = 2 want 9 insertion point 4 below: 4 -> gap |11 - 6| = 5 r = 4 want 7 insertion point 4 below: 4 -> gap |11 - 8| = 3 r = 6 want 5 insertion point 4 below: 4 -> gap |11 - 10| = 1

answer 1 ```

### Constraints - 1 <= n <= 40 - 0 <= each number <= 10^9 - 0 <= target <= 4 * 10^10 - Totals and the target reach 4 * 10^10 and need a signed 64-bit type, because the value searched for can be negative.