Find Original Array From Doubled Array
An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.
Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.
Example 1
Input
changed = [1,3,4,2,6,8]Output
[1,3,4]One possible original array is [1, 3, 4] because twice the values 1, 3, and 4 are 2, 6, and 8, respectively.
Example 2
Input
changed = [6,3,0,1]Output
[]changed is not a doubled array.
Constraints
- 1 <= changed.length <= 10^5
- 0 <= changed[i] <= 10^5