[Java] Array of doubled pairs

Given an array of integers return true if it is possible to reorder its elements in pairs so that arr[2 * i + 1] = 2 * arr[2 * i] for all i up to length/2

In other words, given an array of integers allowing negatives and duplicates, find if it is possible to use each element in a pair where the first element in the pair is half the value of the second element of that pair. Elements cannot be reused among different pairs.

From the description, we need pairs of elements where the second element in a pair must be double the first element:

arr[2 * i + 1] = 2 * arr[2 * i]
 

means for i = 0
 

arr[1] = 2 * arr[0]
 

or
 

arr[0] = arr[1] / 2

Examples:

5,1,2,4
Cannot be done since (1,2) or (2,4) would be a valid pair but we leave in any case 5 without a pair

4,2,2,1
Can be done using pairs (1,2), (2,4)

-4,1,2,-2
Can be done using pairs (-4,-2), (1,2)

-5,1,2,4
Cannot be done since -5/2 does not exist as integer and -10 is not in the array so there is no pair with -5 available

We notice that the smallest element only has one option for a pair: an element that's its double, while the biggest element has only one option for the pair: an element that's its half, every other element instead has 2 choices, either pair with an element that's its double or its half.

We can start by sorting the array in increasing order so that all smaller elements are first, we try and search for each of them their double. If we can't find a double, there is no possibility to make a pair, therefore we stop and return failure.

When we look for a double, we need to apply some logic:
- if element is negative its double is actually element / 2
- if element is positive its double is element * 2

We can count how many times does each element appear in the array to know how many times we have it available to use in a pair, either as first or second element.

Then we scan the array another time and for each element check whether a valid double exists (only necessary for negative numbers) and if it exists, whether it's still available.

If an element cannot be paired, then there is no solution as we were going from the smallest elements up so the only pairing chance is with an element that's its double.

This approach works in O(N log N) time and O(N) space.

You can check my implementation of arrayOfDoubledPairs on my Gist along with some tests in ArrayOfDoubledPairsJTests.