Recover the original array when the given array contains each original value and its doubled value, or determine that it is impossible.
Problem
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.
Goal
Find an array original such that:
changedcontains exactly the numbers fromoriginal- and also contains exactly the numbers
2 * xfor everyxinoriginal
The elements may appear in any order in changed.
If multiple answers are possible, returning any one of them is acceptable.
Input Format
- The input is an integer array
changed. changed[i]is the value at indexi.- The array length is even.
Output Format
- Return an integer array representing one valid original array.
- If reconstruction is impossible, return an empty array
[].
Constraints
changed.lengthis even.- The values in
changedmay be positive, negative, or zero. - A valid original array must have length
changed.length / 2. - If the number of zeros is odd, reconstruction is impossible.
- Use integer arithmetic when checking doubles.
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.
Show 1 more example
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
Unlock deeper context for this problem
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.