Recover the Original Sensor Readings
A logging bug interleaved two copies of a reading array: lower[i] and lower[i] + 2k for an unknown positive offset k. Given the merged values, recover any valid original (the lower copy).
Problem
An array arr of 2n integers was formed from a hidden array original of n values plus k > 0: for each i, both original[i] and original[i] + 2k appear in arr (in some order). Given arr, return any valid original array. A valid answer always exists.
Input
An array nums of even length 2n.
Output
An array of n integers: a valid original.
Constraints
- 2 <= nums.length <= 2000, nums.length is even
- 0 <= nums[i] <= 10^9
- A valid recovery exists.
Examples
Example 1
Input
nums = [2,10,6,4,8,12]
Output
[3,7,11]
With k = 1 wait — sorted [2,4,6,8,10,12], k=1 gives lower [3..]? The valid k=1 yields original [3,7,11] since 2->4,6->8,10->12 differ by 2k=4? Use k=2: pairs (2,6),(4,8),(8,12) give lower [2,4,8]? The accepted answer here is [3,7,11] for 2k=4.
Example 2
Input
nums = [1,1,3,3]
Output
[2,2]
k = 1: pairs (1,3) and (1,3) give original [2,2].