How to get original array from random shuffle of an array-CodePudding

I was asked in an interview today below question. I gave O(nlgn) solution but I was asked to give O(n) solution. I could not come up with O(n) solution. Can you help?

An input array is given like [1,2,4] then every element of it is doubled and 
appended into the array. So the array now looks like [1,2,4,2,4,8].  How 
this array is randomly shuffled. One possible random arrangement is 
[4,8,2,1,2,4].  Now we are given this random shuffled array and we want to
 get original array [1,2,4] in O(n) time. How can I do it?

CodePudding user response：

def findOriginalArray(self, changed: List[int]) -> List[int]:
    size = len(changed)
    ans = []
    left_elements = size//2
    
    #IF SIZE IS ODD THEN RETURN [] NO SOLN. IS POSSIBLE
    if(size%2 !=0):
        return ans
    
    #FREQUENCY DICTIONARY given array [0,0,2,1] my map will be: {0:2,2:1,1:1}
    d = {}
    for i in changed:
        if(i in d):
            d[i] =1
        else:
            d[i] = 1
            
    # CHECK THE EDGE CASE OF 0         
    if(0 in d):
        count = d[0]
        half = count//2
        if((count % 2 != 0) or (half > left_elements)):
            return ans
        left_elements -= half
        ans = [0 for i in range(half)] 
        
    #CHECK REST OF THE CASES : considering the values will be 10^5
    for i in range(1,50001):
        if(i in d):
            if(d[i] > 0):
                count = d[i]
                if(count > left_elements):
                    ans = []
                    break
                left_elements -= d[i]
                for j in range(count):
                    ans.append(i)
                if(2*i in d):
                    if(d[2*i] < count):
                        ans = []
                        break
                    else:
                        d[2*i] -= count
                else:
                    ans = []
                    break
    return ans

CodePudding user response：

I have a simple idea which might not be the best, but I could not think of a case where it would not work. Having the array A with the doubled elements and randomly shuffled, keep a helper map. Process each element of the array and, each time you find a new element, add it to the map with the value 0. When an element is processed, increment map[i] and decrement map[2*i]. Next you iterate over the map and print the elements that have a value greater than zero.

A simple example, say that the vector is:

[1, 2, 3]

And the doubled/shuffled version is:

A = [3, 2, 1, 4, 2, 6]

When processing 3, first add the keys 3 and 6 to the map with value zero. Increment map[3] and decrement map[6]. This way, map[3] = 1 and map[6] = -1. Then for the next element map[2] = 1 and map[4] = -1 and so forth. The final state of the map in this example would be map[1] = 1, map[2] = 1, map[3] = 1, map[4] = -1, map[6] = 0, map[8] = -1, map[12] = -1.

Then you just process the keys of the map and, for each key with a value greater than zero, add it to the output. There are certainly more efficient solutions, but this one is O(n).