Skip to content

954. Array of Doubled Pairs

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

Solutions

Solution 1

Thinking

Reorder the array so each even index is half of the next. Zeros pair only with zeros; an odd count fails. Other values should match from small absolute value to large: each \(x\) must find enough remaining \(2x\), or a larger number may already have been claimed. A frequency map tracks leftovers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int& v : arr) ++freq[v];
        if (freq[0] & 1) return false;
        vector<int> keys;
        for (auto& [k, _] : freq) keys.push_back(k);
        sort(keys.begin(), keys.end(), [](int a, int b) { return abs(a) < abs(b); });
        for (int& k : keys) {
            if (freq[k * 2] < freq[k]) return false;
            freq[k * 2] -= freq[k];
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
}

Comments