✅☑️ Best C++ 5 Solution || Binary Search || XOR || Hash Table || Brute Force->Optimize.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can solve this question using Multiple Approaches. (Here I have explained all the po
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can solve this question using Multiple Approaches. (Here I have explained all the possible solutions of this problem).\n\n1. Solved using Array(Two Nested Loop). Brute Force Approach.\n2. Solved using Array + Hash Table(Unordered map).\n3. Solved using Linear Search.\n4. Solved using Bit Manipulation(xor).\n5. Solved using Binary Search. Optimized Approach.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can easily understand the All the approaches by seeing the code which is easy to understand with comments.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity is given in code comment.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity is given in code comment.\n\n# Code\n```\n/*\n\n    Time Complexity : O(N^2), Here Two nested loop creates the time complexity. Where N is the size of the\n    Array(nums).\n\n    Space Complexity : O(1), Constant space.\n\n    Solved using Array(Two Nested Loop). Brute Force Approach.\n\n    Note : this will give TLE.\n\n*/\n\n\n/***************************************** Approach 1 *****************************************/\n\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size();\n        for(int i=0; i<n; i++){\n            int count = 0;\n            for(int j=0; j<n; j++){\n                if(nums[i] == nums[j]) count++;\n            }\n            if(count == 1) return nums[i];\n        }\n        return -1;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), Here we are doing N iteration which creates the time complexity. Where N is the size\n    of the array(nums).\n\n    Space Complexity : O(N), Hash Table(unordered map) space.\n\n    Solved using Array + Hash Table(unordered map).\n\n*/\n\n\n/***************************************** Approach 2 *****************************************/\n\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        unordered_map<int, int> map;\n        for(auto num : nums){\n            map[num]++;\n        }\n        for(auto num : map){\n            if(num.second == 1) return num.first;\n        }\n        return -1;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), because in the worst case we traverse the <= N element. Where N is the size of the\n    Array(nums).\n                    \n    Space Complexity : O(1), the space complexity is constant.\n\n    Solved using Linear Search.\n\n*/\n\n\n/***************************************** Approach 3 *****************************************/\n\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size();\n        for(int i=0; i<n-1; i+=2){\n            if(nums[i] != nums[i+1]){\n                return nums[i];\n            }\n        }\n        return nums[n-1];\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), because in the worst case we traverse the <= N element. Where N is the size of the\n    Array(nums).\n                    \n    Space Complexity : O(1), the space complexity is constant.\n\n    Solved using Bit manupulation(xor).\n\n*/\n\n\n/***************************************** Approach 4 *****************************************/\n\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int Xor = 0;\n        for(auto num : nums){\n            Xor ^= num;\n        }\n        return Xor;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(log N), since we have used binary search to find the target element. The time complexity\n    is logarithmic.\n\n    Space Complexity : O(1), since we stored only some constant number of elements, the space complexity is\n    constant.\n\n    Solved using Binary Search.\n\n*/\n\n\n/***************************************** Approach 5 *****************************************/\n\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int low = 0, high = nums.size()-1;\n        while(low < high){\n            int mid = (low + high) >> 1;\n            int num = (mid%2==0) ? mid+1 : mid-1;\n            if(nums[mid] == nums[num]) low = mid+1;\n            else high = mid;\n        }\n        return nums[low];\n    }\n};\n\n```\n\n***IF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.***\n\n![WhatsApp Image 2023-02-10 at 19.01.02.jpeg](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)
['Array', 'Hash Table', 'Binary Search', 'Bit Manipulation', 'C++']