615. The Pair That Almost Cancels
Given n integers, choose two of them by position and print the sum whose absolute value is
smallest.
If a positive and a negative sum have the SAME absolute value, print the positive one.
1 60 -10 70 -80 85 -> 5 from -80 + 85
-1 1 -> 0
## The sweep
Sort, put i at the front and j at the back, and keep the best sum seen:
while i < j:
s = a[i] + a[j]
update best with s
if s < 0: i += 1 the sum is too low, so raise it
else: j -= 1 the sum is at or above zero, so lower it
## Why this finds the best
At any moment, a[i] is the smallest value still in play and a[j] the largest.
If s < 0, then a[i] paired with anything still available gives a sum at most s, since
a[j] is the largest partner left. Every one of those is at least as far from zero as s is,
so nothing better involves a[i], and discarding it is safe.
If s >= 0, the mirror argument retires a[j].
This is problem 605 with "equals the target" replaced by "closest to the target", and the target fixed at zero. The shape does not change.
## The tie, and why it needs a rule
1 2 -4 1 reaches both -2 and 2, from 2 + (-4) and 1 + 1. Both are two away from
zero, so without a stated rule two correct programs print different answers.
The statement fixes the positive one. Compare absolute values first, and on equality take the larger sum.
Note this is the OPPOSITE convention to problem 607, which takes the smaller on a tie. That is deliberate: the rule is whatever the statement says, not something to be remembered from another problem, and an implementation that copies 607's comparison fails here.
## Boundaries
Two elements give one pair, whatever it sums to. -1 -1 answers -2, which is a reminder
that the best sum need not be near zero at all.
Sums reach 2 * 10^9 in magnitude. Check that against the limit rather than assuming: a
signed 32 bit integer runs from -2147483648 to 2147483647, so both 2000000000 and
-2000000000 FIT, with about seven percent to spare. This problem has no overflow.
There is a smaller trap next door that is real. Ranking candidates by magnitude means taking
an absolute value, and abs of -2147483648 does not fit in a signed 32 bit integer, so
that is the one input which breaks the call. It cannot arise here, because no sum reaches
past -2 * 10^9, but being able to say WHY it cannot is the part worth having.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `2 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the two-value sum nearest zero, the positive one on a tie.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.