An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

&nbsp;
Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].


Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.


Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.


&nbsp;
Constraints:


	1 &lt;= changed.length &lt;= 105
	0 &lt;= changed[i] &lt;= 105


class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        counter = collections.Counter(changed)
        res = []
        for k in counter.keys():
            
            if k == 0:
                # handle zero as special case
                if counter[k] % 2 > 0:
                    return []
                res += [0] * (counter[k] // 2)
                
            elif counter[k] > 0:
                x = k
                
                # walk down the chain
                while x % 2 == 0 and x // 2 in counter:
                    x = x // 2
                    
                # walk up and process all numbers within the chain. mark the counts as 0
                while x in counter:
                    if counter[x] > 0:
                        res += [x] * counter[x]
                        if counter[x+x] < counter[x]:
                            return []
                        counter[x+x] -= counter[x]
                        counter[x] = 0
                    x += x
        return res
class Solution {
    public int[] findOriginalArray(int[] changed) {

        Arrays.sort(changed);

        if(changed.length%2!=0) return new int[0];

        int mid = changed.length/2;

        int[] res = new int[mid];

        int[] freq = new int[100001];

        for(int no : changed)
            freq[no]++;

        int idx=0;

        for(int no: changed){
            if(freq[no] > 0 && no*2 <= 100000 && freq[no*2]>0){
                freq[no]--;
                freq[no*2]--;
                res[idx++] = no;
            }
        }

        for(int i=0; i<freq.length; i++){
            if(freq[i]!=0) return new int[0];
        }

        return res;

    }
}
class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        unordered_map<int, int> freq;
        for (auto num : changed) freq[num]++;
        
        sort(changed.begin(), changed.end());
        
        vector<int> res;
        for (auto num : changed) {
            if (freq[num] && freq[num*2]) {
                freq[num]--;
                freq[num*2]--;
                res.push_back(num);
            }
        }
        
        for (auto [a, b] : freq)
            if (b) return {};
        
        return res;
    }
};
// Idea is to sort the input array first then start traversing the array
// now if we saw half of the current element before and that half is unmatched then
// match both of them otherwise note the occurence of current element inorder
// to match it with its double element in the future

// Time -> O(nlogn) due to sorting
// Space -> O(n) due to map

/**
 * @param {number[]} changed
 * @return {number[]}
 */
var findOriginalArray = function(changed) {
    
    const n = changed.length
    if(n%2 === 1) return []
    
    let original = []
    let map = new Map()
    
    changed.sort((a,b) => {
        return a-b
    })
    
    for(let ele of changed) {
        const half = ele/2
        if(map.has(half) && map.get(half) > 0) {
            original.push(half)
            map.set(half, map.get(half)-1)
        } else {
            map.set(ele, map.has(ele) ? map.get(ele)+1: 1)
        }
    }
    
    if(original.length !== n/2) return []
    
    return original
};
Find Original Array From Doubled Array