Array of Doubled Pairs

Problem Statement

The objective is to determine if it is possible to reorder an integer array arr, which has an even length, in such a way that for every valid index i (where 0 <= i < len(arr) / 2), the relation arr[2 * i + 1] = 2 * arr[2 * i] holds. Essentially, this condition means that for each pair of elements in the reordered array, the second element should exactly be double the first element. The function should return true if such a reordering is possible and false otherwise.

Examples

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

Approach and Intuition

To solve this problem, we need to determine if we can pair elements such that in each pair, the second element is exactly double the value of the first. The idea of reordering suggests that any element x in the array should have a corresponding 2x to fulfill the requirement.

1. Since pair formation requires exactly a double relationship, the presence of each element must be checked against the presence of its double (or half, depending on the value and sign).

2. Sorting the array can be an initial step. Sorting helps in linearly checking for pairs because once sorted, any valid pair (x, 2x) will be adjacent or at a predictable position in the sequence.

3. Counting the frequency of elements is another cornerstone strategy; this approach helps track how many times an element and its double appear in the array, ensuring that we can indeed form pairs as required.

4. Iterate over the sorted and filtered list (considering only those elements that can have a valid pair) and attempt to decrement the count for each element and its required pair. If at any point a required double can't be met from current available counts, return false.

5. Post iteration, if all pairs are successfully counted and matched according to the rule, return true.

The sorted approach, combined with counting, ensures a valid search for pairs in an efficient manner, adhering to given constraints and array properties. This method leverages sorting and hashing (for counts) to reach an optimal solution in terms of complexity and execution time.

Solutions

class Solution {
    public boolean canFormPairs(int[] array) {
        // frequency stores number of occurrences of each integer in array
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int num : array)
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);

        // Sorted array based on the absolute values
        Integer[] sortedArray = new Integer[array.length];
        for (int i = 0; i < array.length; ++i)
            sortedArray[i] = array[i];
        Arrays.sort(sortedArray, Comparator.comparingInt(Math::abs));

        for (int num : sortedArray) {
            // Ignore this number if already paired
            if (frequency.get(num) == 0) continue;
            // Check for the double presence
            if (frequency.getOrDefault(2 * num, 0) <= 0) return false;

            // Decrease the count for both num and its double
            frequency.put(num, frequency.get(num) - 1);
            frequency.put(2 * num, frequency.get(2 * num) - 1);
        }

        // Successfully paired all elements
        return true;
    }
}