Recover the original array when the given array contains each original value and its doubled value, or determine that it is impossible.
You are given an integer array changed. It was formed by taking some original array original, then appending 2 * x for every value x in original, and finally shuffling all the elements.
Your task is to reconstruct one possible original array from changed.
If no valid original array exists, return an empty array.
Find an array original such that:
changed contains exactly the numbers from original2 * x for every x in originalThe elements may appear in any order in changed.
If multiple answers are possible, returning any one of them is acceptable.
changed.changed[i] is the value at index i.[].changed.length is even.changed may be positive, negative, or zero.changed.length / 2.Example 1
Input
changed = [1,3,4,2,6,8]
Output
[1,3,4]
Explanation
One valid original array is [1, 3, 4] because doubling each element gives [2, 6, 8], and together they form the shuffled array [1,3,4,2,6,8].
Example 2
Input
changed = [6,3,0,1]
Output
[]
Explanation
No valid original array exists because the values cannot be partitioned into pairs (x, 2x) for all elements.
Example 3
Input
changed = [0,0,1,2]
Output
[0,1]
Explanation
The pair for 0 must be (0,0), and 1 pairs with 2. This reconstructs the original array [0,1].
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.