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

user_16577729 0
Viewed 103

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)?

list algorithm
2 Answers

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<>();
List<Integer> solution = new LinkedList<>();
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.
        solution.add(n);
        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;
user_47851100

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
user_64388190
Related