Найти исходный массив из удвоенного массива

Целочисленный массив преобразуется в удвоенный массив, измененный добавлением удвоенного значения каждого элемента в исходном, а затем случайным образом перемешанный.

Дан изменненый массив, необходимо вернуть исходный, если это возможно. Если это невозможно, верните пустой массив. Элементы в оригинале могут быть в любом порядке.

Входные данные: элементы массива - целые числа от 0 до 10000. Размер массива от 1 до 10000.

Примеры:

1. changed = [1, 3, 4, 2, 6, 8]
   Output: [1, 3, 4]
   Пояснение: [1, 3, 4, 1 * 2, 3 * 2, 4 * 2] = [1, 3, 4, 2, 6, 8]
2. changed = [6, 3, 0, 1]
   Output: []
   Пояснение: невозможно получить подобный удвоенный массив.

Разбор

Очевидно, что если исходный массив - это удвоенный массив, то количество его элементов должно быть четным. В противном случае мы сразу можем вернуть пустой массив в качестве ответа.

Элементы в результирующем массиве можно вернуть в любом порядке, поэтому мы можем отсортировать исходный массив для удобства.

Далее мы для каждого элемента в массиве проверяем, есть ли удвоенный элемент для него.

Детали реализации смотрите ниже.