Algorithm
Problem Name: 954. Array of Doubled Pairs
Problem Link: https://leetcode.com/problems/array-of-doubled-pairs/
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 * 104arr.lengthis even.-105 <= arr[i] <= 105
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const canReorderDoubled = function(A) {
const cnt = {}
for(let val of A) {
val = Math.abs(val)
cnt[val] ? cnt[val]++ : cnt[val] = 1
}
for(let val in cnt) {
let sibling = val * 2
if(val == '0') {
if(cnt[val] % 2) return false
cnt[val] = 0
} else if(cnt[val] && cnt[sibling]) {
cnt[sibling] -= cnt[val]
cnt[val] = 0
}
}
for(let val in cnt)
if(cnt[val]) return false
return true
};
Input
arr = [3,1,3,6]
Output
false
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def canReorderDoubled(self, A):
cnt = collections.Counter(A)
for a in sorted(A, key = abs):
if cnt[a] and cnt[a * 2]:
cnt[a] -= 1
cnt[a * 2] -= 1
elif cnt[a] and a % 2 == 0 and cnt[a // 2]:
cnt[a] -= 1
cnt[a // 2] -= 1
return all(cnt[a] == 0 for a in A)
Input
arr = [3,1,3,6]
Output
false