動機

  1. 乖乖sort
  2. 用到整數除法注意奇數

Problem

Given an array of integers arr of even length, return true if and only if it is possible to reorder it such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2.

 

Example 1:

Input: arr = [3,1,3,6]Output: false

Example 2:

Input: arr = [2,1,2,6]Output: false

Example 3:

Input: arr = [4,-2,2,-4]Output: trueExplanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: arr = [1,2,4,16,8,4]Output: false

 

Constraints:

  • 0 <= arr.length <= 3 * 104
  • arr.length is even.
  • -105 <= arr[i] <= 105

Sol

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        cnts = Counter(arr)
        
        ks = sorted(list(cnts.keys()))
        for k in ks:
            for _ in range(cnts[k]):
                for n in ([k*2,k//2] if k % 2 == 0 else [k*2]):
                    if n in cnts:
                        if cnts[n] == 1:
                            del cnts[n]
                        else:
                            cnts[n] -= 1
                        if cnts[k] == 1:
                            del cnts[k]
                        else:
                            cnts[k] -= 1
        return not cnts