#2007
Find Original Array From Doubled Array
specialist · 995 · lc medium +32 · verified · 40.8% accepted · 2,562 likes · top 20%
Description
A "doubled array" is formed from some array original by appending 2 * x for each element x, then shuffling. Given the resulting changed, reconstruct and return original in any order, or return an empty array if changed is not a valid doubled array.
Example 1:
Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].
Example 2:
Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.
Example 3:
Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.
Code
1
2
3