Skip to content

954. Array of Doubled Pairs

Difficulty Topics

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

array-of-doubled-pairs.py
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