##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/954.html

# 954. Array of Doubled Pairs (Medium)

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

Example 1:

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


Example 2:

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


Example 3:

Input: [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].


Example 4:

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


Note:

1. 0 <= A.length <= 30000
2. A.length is even
3. -100000 <= A[i] <= 100000

Companies:

Related Topics:
Array, Hash Table

## Solution 1. Greedy

// OJ: https://leetcode.com/problems/array-of-doubled-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
multiset<int> s(A.begin(), A.end());
while (s.size()) {
int val = *s.begin();
if (val < 0 && val % 2) return false;
int next = val >= 0 ? val * 2 : val / 2;
s.erase(s.begin());
auto it = s.find(next);
if (it == s.end()) return false;
s.erase(it);
}
return true;
}
};

• class Solution {
public boolean canReorderDoubled(int[] A) {
List<Integer> list = new ArrayList<Integer>();
int length = A.length;
for (int i = 0; i < length; i++)
Collections.sort(list, new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
if (Math.abs(num1) != Math.abs(num2))
return Math.abs(num1) - Math.abs(num2);
else
return num1 - num2;
}
});
while (list.size() > 0) {
int num = list.remove(0);
int num2 = num * 2;
int index = list.indexOf(num2);
if (index >= 0)
list.remove(index);
else
return false;
}
return true;
}
}

############

class Solution {
public boolean canReorderDoubled(int[] arr) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : arr) {
freq.put(v, freq.getOrDefault(v, 0) + 1);
}
if ((freq.getOrDefault(0, 0) & 1) != 0) {
return false;
}
List<Integer> keys = new ArrayList<>(freq.keySet());
keys.sort(Comparator.comparingInt(Math::abs));
for (int k : keys) {
if (freq.getOrDefault(k << 1, 0) < freq.get(k)) {
return false;
}
freq.put(k << 1, freq.getOrDefault(k << 1, 0) - freq.get(k));
}
return true;
}
}

• // OJ: https://leetcode.com/problems/array-of-doubled-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
multiset<int> s(A.begin(), A.end());
while (s.size()) {
int val = *s.begin();
if (val < 0 && val % 2) return false;
int next = val >= 0 ? val * 2 : val / 2;
s.erase(s.begin());
auto it = s.find(next);
if (it == s.end()) return false;
s.erase(it);
}
return true;
}
};

• class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
freq = Counter(arr)
if freq[0] & 1:
return False
for x in sorted(freq, key=abs):
if freq[x << 1] < freq[x]:
return False
freq[x << 1] -= freq[x]
return True

############

class Solution(object):
def canReorderDoubled(self, A):
"""
:type A: List[int]
:rtype: bool
"""
A.sort()
N = len(A)
count = collections.Counter(A)
for i in range(N):
if A[i] == 0 or A[i] not in count: continue
elif A[i] < 0:
if A[i] % 2 == 1 or count[A[i] / 2] == 0:
return False
else:
count[A[i] / 2] -= count[A[i]]
if count[A[i] / 2] == 0:
del count[A[i] / 2]
del count[A[i]]
else:
if count[A[i] * 2] == 0:
return False
else:
count[A[i] * 2] -= count[A[i]]
if count[A[i] * 2] == 0:
del count[A[i] * 2]
del count[A[i]]
return True

• func canReorderDoubled(arr []int) bool {
freq := make(map[int]int)
for _, v := range arr {
freq[v]++
}
if freq[0]%2 != 0 {
return false
}
var keys []int
for k := range freq {
keys = append(keys, k)
}
sort.Slice(keys, func(i, j int) bool {
return abs(keys[i]) < abs(keys[j])
})
for _, k := range keys {
if freq[k*2] < freq[k] {
return false
}
freq[k*2] -= freq[k]
}
return true
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}