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:
0 <= A.length <= 30000A.lengthis even-100000 <= A[i] <= 100000
Companies:
Google
Related Topics:
Array, Hash Table
// OJ: https://leetcode.com/problems/array-of-doubled-pairs/
// Author: github.com/lzl124631x
// 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;
}
};