✅ [C++] EASY Intuitive Solution|| 2 approaches || Binary Search || TC:O(log(N)), SC:O(1)
Hello everyone, I hope you all are doing great!\n\nNOTE: If you found this post helpful, then please do upvote it!\n\nBrute Force Approach: (XOR) Since we know 
Hello everyone, I hope you all are doing great!\n\n***NOTE: If you found this post helpful, then please do upvote it!***\n\n**Brute Force Approach: (XOR)** Since we know every element occurs exactly twice, where as our target element occurs once, then we can simple take xor of all the elements of the array. In the end we will be left with our target element that appeared once (Because A^A = 0).\n\n**Code:**\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size();\n        int xr{};\n        \n        for(auto num: nums)\n            xr = xr^num;\n        \n        return xr;\n    }\n};\n```\n\n**Time Complexity:** ***O(N)***\n**Space Complexity:** ***O(1)***\n\n<hr></hr>\n\n**Optimal Approach: (Binary Search)**\n1. We will use the fact that the vector is sorted.\n2. **Observation:** If you divide the array in two parts, `PART A`: where elements are before target element and `PART B`:  where elements are after target element then:\n\n\ta. In `PART A`, the first instance of element occurs at even index and the second instance of the element occurs at odd index.\n\t\n\tb. In `PART B`, the first instance of element occurs at odd index and the second instance of the element occurs at even index.\n\t\n\tc. You can visualize using following example: \n\t```\n\tindex:   0 1 2 3 4 5 6 7 8\n\tvector: [1,1,2,3,3,4,4,8,8]\n\t             \uD83D\uDC46 (Target element is 2 since it appears once)\n\t```\n\tIn this example, before `2` every first instance of element occurs at even index and second instance at odd index (see element `1`) and after `2` every first instance of element occurs at odd index and second instance at even index (see element `3`, `4` and `8`).\n\t\n\t3. So from the above observation we will apply binary search on our array, and if we are on the `PART - B` side of array, we go to left, otherwise we go right.\n\n**Code:**\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int low = 0, high = nums.size()-2; \n        \n        while(low <= high){\n            \n            int mid = low + (high-low)/2;\n            \n\t\t\t// If we are on left side, move right\n            if(nums[mid] == nums[mid^1]) low = mid+1;\n\t\t\t// if we are on right side, move left\n            else high = mid-1;\n        }\n        \n        return nums[low];\n    }\n};\n\n// mid^1 explanation:\n// If mid is odd then (mid^1) will always be the even number before mid\n// If mid is even then (mid^1) will always be the odd number after mid\n\n// And hence I am able to check whether mid is in left half or right half as:\n\n// Suppose mid is odd: then mid^1 will give even number before it, \n// then if nums[mid] == nums[mid^1] \n// then 1st instance at even (mid^1) and 2nd instance at odd (mid), \n// hence we are on left side otherwise we are on right side.\n\n// Suppose mid is even: then mid^1 will give odd number after it, \n// then if nums[mid] == nums[mid^1]\n// then 1st instance at even (mid) and 2nd instance at odd (mid^1), \n// hence we are on left side otherwise we are on right side\n```\n\n**Time Complexity:** ***O(Log(N))***\n**Space Complexity:** ***O(1)***\n\n**NOTE: Please \uD83D\uDD3C Upvote if you found this post helpful**
[]