Recover Entries from a Shuffled Doubled Multiset
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
An original array is doubled by appending twice every original value and then shuffling all entries. Given the nonnegative array `changed`, return any original array that could produce it, or an empty array if no such original exists. Any ordering of a valid recovered array is acceptable.
```cpp
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed);
};
```
### Examples
**Example 1:**
```text
changed = [4,0,2,0]
Output: [0,2]
Explanation: Appending doubles [0,4] gives the same multiset.
```
**Example 2:**
```text
changed = [2,2,4,7]
Output: []
Explanation: One 2 can pair with 4, but the remaining values cannot be paired as value and double.
```
### Constraints
- `1 <= changed.length <= 10^5`.
- `0 <= changed[i] <= 10^5`.
### Clarifying Questions
Multiplicities matter, including pairs of zeros. Any ordering of a valid recovered array is accepted.
```hint Inspect the structure
For nonnegative entries, which remaining value must serve as an original rather than somebody else's double?
```
### What a Strong Answer Covers
- Account for every input occurrence exactly once in the original-and-double construction, including repeated zeros.
- Detect impossible inputs and preserve the source freedom to return valid recovered entries in any order.
### Follow-up Questions
What changes if negative values are permitted?
Overview: Recover Entries from a Shuffled Doubled Multiset. A doubled array consists of every original entry together with twice each original value, shuffled into arbitrary order. Given nonnegative changed, return any original array consistent with this construction, or an empty array if impossible. The recovered entries may be returned in any order.