Undo the Doubling

Medium

Someone took an integer array, appended twice the value of each of its elements, and then shuffled the whole thing. The result is mixed. Recover the original array. If mixed could not have been produced this way, return an empty list. The elements of the original array may be returned in any order.

Example 1

mixed=[10, 3, 5, 6] → [3, 5]

The original was [3, 5]: 6 and 10 were added and everything got shuffled.

Example 2

mixed=[4, 2, 2, 8] → []

One 2 pairs with the 4, but the other 2 and the 8 are left without partners, so this cannot be a doubled array.

Example 3

mixed=[0, 0, 7, 14] → [0, 7]

Constraints

1 ≤ len(mixed) ≤ 3 · 10⁵
0 ≤ mixed[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table Sorting

Similar problems

Jobs With a Cooldown Medium Deal Into Consecutive Sets Medium Pair Each Number With Its Double Medium Spread Out the Labels Medium Pick Within Tag Limits Medium

Input

mixed=[10, 3, 5, 6]

Expected

[3, 5]

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.