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

Form analysis 0 forms found in the DOM

Text 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])