# What is the optimal solution to reversing: append doubled list and randomizing?

Solution for What is the optimal solution to reversing: append doubled list and randomizing?
is Given Below:

I am looking at this challenge:

A function takes a list of numbers, extends that list with the doubles of those numbers and then shuffles the result randomly.

Example:

`````` [1,2,4] > [1,2,4,2,4,8] > [8,4,1,2,2,4]
``````

Write a function that takes a potential output list and returns the original list. Return `none` if no such possible original list exists.

### Examples

``````[8,4,1,2,2,4] > [1,2,4]

[1,4,2] > None
``````

I can see an O(nlogn) solution by sorting and then using a hashmap to keep track of doubles to skip every time you come across a new original number.

Is there a faster solution (perhaps linear)?

The problem is solvable in O(n). But you have to be careful. Every chain of doubles (1,2,4,8 would be a chain) has to be resolved in the end and not on the fly, otherwise you end up with wrong results.

1. Add all values to a hash map (the value as key and the number of occurences as value).

2. Pick any key from the map (n). As long as n/2 exists as key in the map set n = n/2 and try again. Like this you find the start of the chain.

3. If n * 2 is not in the map there is no solution.

4. Add n to the solution and decrease the values for n and n * 2 in the map, if they are 0 remove them.

5. If n is still in the map continue with 3. If n * 2 is in the map n = n * 2 and continue with 3. If n * 4 is in the map n = n * 4 and continue with 3. Otherwise continue with 2.

I am pretty sure that this is about O(3n) = O(n), because 1. is O(n), 2. is also O(n) because after finding the start of a chain it will be removed completely and 4. and 5. is also O(n).

In code (some edge cases are not mentioned above, but handled in the code, like 0):

``````Map<Integer, Integer> map = new HashMap<>();
for (int i : list) map.put(i, map.containsKey(i) ? map.get(i) + 1 : 1); // 1.
while (!map.isEmpty()) {
int n = map.keySet().iterator().next(); // 2.
while (n != 0 && n % 2 == 0 && map.containsKey(n / 2)) n /= 2;
outer:
for (;;) {
if (!map.containsKey(n * 2)) return null; // 3.
if (n == 0) { // edge case 0
if (map.get(0) < 2) {
return null;
} else if (map.get(0) == 2) {
map.remove(0);
break;
} else {
map.put(0, map.get(0) - 2);
continue;
}
}
for (int i = n; i <= 2 * n; i += n) { // 4.
if (map.get(i) == 1) map.remove(i);
else map.put(i, map.get(i) - 1);
}
for (int i = n; i <= n * 4; i *= 2) { // 5.
if (map.containsKey(i)) {
n = i;
continue outer;
}
}
break;
}
}
return solution;
``````

It’s clear that if we’re prepared to incur the cost of sorting then there’s a simple solution – build a frequency map with sorted keys, e.g. a `TreeMap`, and keep removing the minimum key, which has to be in the original list, and it’s double, until the map is empty or we encounter a key whose double is not in the map, in which case no solution exists.

While we can’t get the global minimum without sorting we can get a series of local minima – i.e. the smallest value in a chain of doubled values. We can identify such local minima by taking each value in the original array and halving it until we can no longer find a value in the map. Once we have the local minima we can proceed as in the case of a sorted map.

``````static int[] doubledArray(int[] a)
{
Map<Integer, Integer> map = new HashMap<>();
for(int k : a) map.put(k, 1 + map.getOrDefault(k, 0));

int[] res = new int[a.length/2];
for(int i=0, j=0; i<a.length; i++)
{
while(map.getOrDefault(a[i], 0) > 0)
{
int k = a[i];
while(k > 0 && map.getOrDefault(k/2, 0) > 0) k /= 2;

if(map.getOrDefault(k*2, 0) == 0) return null;

res[j++] = k;

map.put(k*2, map.get(2*k)-1);
map.put(k, map.get(k)-1);
}
}
return res;
}
``````

Test:

``````int[][] tests = {{8,4,1,2,2,4}, {4,8,16,2}, {2,0,1,0}, {4,3,2,1}};
for(int[] t : tests)
System.out.println(Arrays.toString(t) + " : " + Arrays.toString(doubledArray(t)));
``````

Output:

``````[8, 4, 1, 2, 2, 4] : [1, 2, 4]
[4, 8, 16, 2] : [2, 8]
[2, 0, 1, 0] : [0, 1]
[4, 3, 2, 1] : null
``````