954. Array of Doubled Pairs

Problem Link

Description

---

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

 

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: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

 

Constraints:

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

Solution

---

Python3

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        counter = collections.Counter(arr)
        arr.sort()
        
        for x in arr:
            if counter[x] == 0: continue
            
            if x < 0 and x & 1: return False
            
            t = x * 2 if x > 0 else x // 2
            
            if counter[t] == 0: return False
            
            counter[x] -= 1
            counter[t] -= 1
        
        return True