Published: Sep 15, 2022
This problem needs a frequency table. While checking the doubled value is in the frequency table, the count should be decremented not to use the same value more than once.
An integer array
originalis 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
originalif changed is a doubled array. If
changedis not a doubled array, return an empty array. The elements in
originalmay be returned in any order.
1 <= changed.length <= 10**5
0 <= changed[i] <= 10**5
Example 1: Input: changed = [1,3,4,2,6,8] Output: [1,3,4] Explanation: One possible original array could be [1,3,4], [3,1,4] and any order
Example 2: Input: changed = [6,3,0,1] Output:  Explanation: changed is not a doubled array.
Example 3: Input: changed =  Output:  Explanation: changed is not a doubled array.
The first step is to create a frequency table and sort the given array. Start from smallest value and check its doubled value exists and whose count is more than 0. If it does, add the value to the result array and count down. This way, we get the answer.
class FindOriginalArrayFromDoubledArray: def findOriginalArray(self, changed: List[int]) -> List[int]: freq = collections.Counter(changed) changed.sort() original =  for v in changed: if freq[v]: freq[v] -= 1 twice = v * 2 if twice in freq and freq[twice] > 0: freq[twice] -= 1 original.append(v) else: return  return original