Find Original Array From Doubled Array LeetCode solution in Python

1
class Solution:
2
    def findOriginalArray(self, changed: List[int]) -> List[int]:
3
        counter = collections.Counter(changed)
4
        res = []
5
        for k in counter.keys():
6

7
            if k == 0:
8
                # handle zero as special case
9
                if counter[k] % 2 > 0:
10
                    return []
11
                res += [0] * (counter[k] // 2)
12

13
            elif counter[k] > 0:
14
                x = k
15

16
                # walk down the chain
17
                while x % 2 == 0 and x // 2 in counter:
18
                    x = x // 2
19

20
                # walk up and process all numbers within the chain. mark the counts as 0
21
                while x in counter:
22
                    if counter[x] > 0:
23
                        res += [x] * counter[x]
24
                        if counter[x + x] < counter[x]:
25
                            return []
26
                        counter[x + x] -= counter[x]
27
                        counter[x] = 0
28
                    x += x
29
        return res