<p>Given a <strong>non-empty</strong>&nbsp;array of integers <code>nums</code>, every element appears <em>twice</em> except for one. Find that single one.</p>

<p>You must&nbsp;implement a solution with a linear runtime complexity and use&nbsp;only constant&nbsp;extra space.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [2,2,1]
<strong>Output:</strong> 1
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [4,1,2,1,2]
<strong>Output:</strong> 4
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> nums = [1]
<strong>Output:</strong> 1
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>-3 * 10<sup>4</sup> &lt;= nums[i] &lt;= 3 * 10<sup>4</sup></code></li>
	<li>Each element in the array appears twice except for one element which appears only once.</li>
</ul>

// M-1) Brute force (map) --> T.C: O(n), S.C: O(m) where m is size of the map and m = (n/2)+1.
/*
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        int single;

        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) {   // O(n) for n elements 
                m[nums[i]]++;   // O(1) for single element insertion
        }

        for (auto it : m) {
            if (it.second == 1){
                single = it.first;
                break;
            }   
        }

        return single;
    }
};
*/
// NOTE: Avoid using hashing as there can be negative numbers in nums




// M-2) Optimal approach (XOR)  --> T.C: O(n), S.C: O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        // int single = nums[0];
        // int i = n-1;
        // while(i >= 0){
        //     if(i-1 >= 0 && nums[i] == nums[i-1]){
        //         i -= 2;
        //     }
        //     else{
        //         single = nums[i];
        //         break;
        //     }
        // }
        
        int i = 0, single = 0;
        while(i < n){
            if(i == n-1){
               single = nums[i];
               break; 
            }
            else if(nums[i] != nums[i+1]){
                single = nums[i];
                break;
            }
            else{
                i += 2;
            }
        }

        return single;
    }
};



// M-2) Optimal approach (XOR)  --> T.C: O(n), S.C: O(1)
// class Solution {
// public:
//     int singleNumber(vector<int>& nums) {
//         int n = nums.size();
//         int xorr = 0;

//         for(int i = 0; i < n; i++){     // XOR all the elements:
//             xorr = xorr ^ nums[i];
//         }

//         int single = xorr;
//         return single;
//     }
// };
20800