Array Of Doubled Pairs Problem
Description
LeetCode Problem 954.
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:
1
2
Input: arr = [3,1,3,6]
Output: false
Example 2:
1
2
Input: arr = [2,1,2,6]
Output: false
Example 3:
1
2
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].
Example 4:
1
2
Input: arr = [1,2,4,16,8,4]
Output: false
Constraints:
- 2 <= arr.length <= 3 * 10^4
- arr.length is even.
- -10^5 <= arr[i] <= 10^5
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
unordered_map<int, int> freq;
for (auto num : arr) freq[num]++;
sort(arr.begin(), arr.end());
for (auto num : arr) {
if (freq[num] && freq[num*2]) {
freq[num]--;
freq[num*2]--;
}
}
for (auto [a, b] : freq)
if (b) return false;
return true;
}
};