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

<p>Given an array <code>changed</code>, return <code>original</code><em> if </em><code>changed</code><em> is a <strong>doubled</strong> array. If </em><code>changed</code><em> is not a <strong>doubled</strong> array, return an empty array. The elements in</em> <code>original</code> <em>may be returned in <strong>any</strong> order</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> changed = [1,3,4,2,6,8]
<strong>Output:</strong> [1,3,4]
<strong>Explanation:</strong> 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].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> changed = [6,3,0,1]
<strong>Output:</strong> []
<strong>Explanation:</strong> changed is not a doubled array.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> changed = [1]
<strong>Output:</strong> []
<strong>Explanation:</strong> changed is not a doubled array.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= changed.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= changed[i] &lt;= 10<sup>5</sup></code></li>
</ul>

/*
Approach: normal Sort
We need to pair up elements in the array as explained above. Thus, the first validation we should do is, if the array size is even or not. If it's not we cannot have an answer.
We need to find the smallest element at each iteration. Hence, we can prepare a fred array 
using counting sort, then iterating from left to right will provide us with the smallest 
element. Once we got the smallest element say X we need to check if the element 2X exists 
in the array or not. If the element 2X is present in the freq array we will decrement its 
count else the element X cannot be paired with any other element and hence we return an 
empty array.
T.C. = O(n+k) where n is no of elements in changed and k is size of counting sort array
S.C. O(k)

Counting sort solution
Similar to the previous approach, we will find the smallest element always. 
The only difference here is that instead of sorting the original array using built-in sorting functions we will use counting sort. We will use an array freq to store the frequency of each element in the given array.
Now, we will iterate from 0 to the maximum value that is present in the array. For each element num we will follow the exact same process as we did previously, 
we check for the element 2 * num and proceed accordingly.*/

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        int maxEle = INT_MIN, size = changed.size();
        
        for(int& ele:changed)
        {
            maxEle = max(maxEle, ele);
        }
        vector<int> freq(maxEle+1, 0);
        
        for(int& ele:changed)
        {
            freq[ele]++;
        }
        vector<int> original;
        
        for(int num = 0;num<freq.size();num++)
        {
            if(freq[num]>0)
            {
                freq[num]--;
                if(2*num < freq.size() && freq[2*num]>0)
                {
                    freq[2*num]--;
                    original.push_back(num);
                    num--;
                }
                else
                {
                    return {};
                }
            }
        }
        return original;
    }
};
123505