ix.io
Open in
urlscan Pro
66.172.11.73
Public Scan
URL:
http://ix.io/3WfW
Submission: On April 25 via manual from EG — Scanned from DE
Submission: On April 25 via manual from EG — Scanned from DE
Form analysis
0 forms found in the DOMText Content
from collections import Counter # Key insight: # We have "chains" of doubling like 1 2 4 8. # We are afraid of picking out 2 and 4 as a pair. # # Solution: # Pick some number x. Backtrack to the start of the chain. # We now for sure start at a halve. # Walk along the chain and remove pairs of items. # # We will only remove elements once. # We will traverse every chain at most twice. # So overall time complexity is O(n) def solve(nums): counts = Counter(nums) res = [] for x in nums: if counts[x] == 0: # Already processed continue # Find the start of the chain while x%2 == 0 and counts[x//2] > 0: x //= 2 # Walk along the chain and remove pairs. while counts[x] > 0 and counts[2*x] > 0: res.append(x) counts[x] -= 1 counts[2*x] -= 1 x *= 4 # Check if we have any leftovers, if so the input is invalid. if sum(counts.values()) > 0: return None return res def test(seq, expected): import random random.shuffle(seq) res = solve(seq) if res is None: assert res == expected else: assert sorted(res) == expected test([1, 2, 3], None) test([1, 2, 3, 4], None) test([1, 2, 2, 4], [1, 2]) test([1, 1, 2, 2], [1, 1]) test([1, 2, 4, 8], [1, 4])