✅ [C++/Python] 7 Simple Solutions w/ Explanation | Brute + Hashmap + XOR + Linear +2 Binary Search
We are given a sorted array nums consisting of elements each of which occurs twice except one. We need to return that element which occurs once.\n\n\nTable of C
We are given a sorted array `nums` consisting of elements each of which occurs twice except one. We need to return that element which occurs once.\n\n<details>\n<summary><i>Table of Contents</i></summary>\n<p align=middle>\n<table>\n  <tr>\n    <th>No.</th>\n    <th>Approach</th>\n    <th>Time</th>\n    <th>Space</th>\n  </tr>\n  <tr>\n  <td>1</td>\n  <td>\u26A0\uFE0F\u2714\uFE0F <b>Brute-Force</b></td>\n    <td><code>O(N<sup>2</sup>)</code></td>\n    <td><code>O(1)</code></td>\n  </tr>\n  <tr>\n  <td>2</td>\n    <td>\u2714\uFE0F <b>Hashmap</b></td>\n    <td><code>O(N)</code></td>\n    <td><code>O(N)</code></td>\n  </tr>\n  <tr>\n  <td>3</td>\n    <td>\u2714\uFE0F <b> Hashset</b></td>\n    <td><code>O(N)</code></td>\n    <td><code>O(N)</code></td>\n  </tr>\n  <tr>\n  <td>4</td>\n    <td>\u2714\uFE0F <b>XOR</b></td>\n    <td><code>O(N)</code></td>\n    <td><code>O(1)</code></td>\n  </tr>\n  <tr>\n  <td>5</td>\n    <td>\u2714\uFE0F <b>Linear-Search</b></td>\n    <td><code>O(N)</code></td>\n    <td><code>O(1)</code></td>\n  </tr>\n  <tr>\n  <td>6</td>\n    <td>\u2714\uFE0F <b>Binary Search</b></td>\n    <td><code>O(logN)</code></td>\n    <td><code>O(1)</code></td>\n  </tr>  \n  <tr>\n  <td>7</td>\n    <td>\u2714\uFE0F <b>Binary Search - 2nd Approach</b></td>\n    <td><code>O(logN)</code></td>\n    <td><code>O(1)</code></td>\n  </tr>  \n</table>\n</p>\n</details>\n\n---\n\n\n\n\u26A0\uFE0F \u2714\uFE0F  <em><b>Solution - I (Brute-Force)</b></em>\n\nThe most naive, brute-force way of solving this problem would be to consider each element in `nums` and check how many times it occurs. If it occurs just once, we can return that element as answer.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        for(auto c : nums) {\n            int occurence = 0;\n            for(auto c2 : nums)\n                occurence += c == c2;\n            if(occurence == 1) return c;\n        }\n        return -1;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        for c in nums:\n            if nums.count(c) == 1: \n\t\t\t\treturn c\n```\n\n***Time Complexity :*** **<code>O(N<sup>2</sup>)</code>**, where `N` is the number of elements in the `nums` array. We take `O(N)` time to check occurences of an element in `nums`. In the worst case, there are `N` elements for which this operation is performed giving a total time complexity of <code>O(N<sup>2</sup>)</code>\n***Space Complexity :*** **`O(1)`**\n\n**Note :** The above solution passes for now but that\'s due to weak test cases.\n\n---\n\n\u2714\uFE0F ***Solution - II (Hashmap)***\n\nWe can use a hashmap to iterate over the `nums` array and count the number of times each element occurs. Finally, the element that has frequency of 1 will be returned.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        unordered_map<int, int> mp;\n        for(auto c : nums) mp[c]++;                // counting frequency of elements\n        for(auto [c, freq] : mp)\n            if(freq == 1) return c;                // return element occuring once\n        return -1;                                 // wont be reached\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        mp = Counter(nums)\n        for c, freq in mp.items():\n            if freq == 1: \n                return c\n```\n\n\n***Time Complexity :*** **`O(N)`**, where `N` is the number of elements in the `nums` array. We required `O(N)` time to iterate over `nums` and populate hashmap and another `O(N)` to iterate over the hashmap.\n***Space Complexity :*** **`O(N)`**, required to maintain the hashmap.\n\n---\n\n\u2714\uFE0F ***Solution - III (Hashset)***\n\nWe can do slightly better on average space complexity by using a hashset. Since every element occurs twice except one, we can insert into set when we find 1st occurence and remove from set when its found again. Finally the set will consist of only 1 element which will be the required answer.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        unordered_set<int> s;\n        for(auto c : nums) \n            if(s.count(c)) s.erase(c);      // erase on 2nd occurence\n            else s.insert(c);               // insert on 1st occurence\n        return *begin(s);                   // only element at end is the element occuring once\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        s = set()\n        for c in nums:\n            if c in s: s.remove(c)\n            else: s.add(c)\n        return s.pop()\n```\n\n***Time Complexity :*** **`O(N)`**\n***Space Complexity :*** **`O(N)`**, required to maintain the hashset. Here the average case complexity is `O(N/2)`, slight improvement from `O(N)` in case of hashmap.\n\n---\n\n\u2714\uFE0F ***Solution - IV (XOR)***\n\nWe can use the property of xor operation in this problem. We know that `a \u2295 a = 0`, i.e, two same numbers when xor-ed, cancels each other out. In our case, every element occurs twice except the one. Thus, if we xor all the elements from `nums`, every element will cancel each other out except the required answer.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int ans = 0;\n        for(auto c : nums) ans ^= c;    // xor-ing all elements of array\n        return ans;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        return reduce(xor, nums)\n```\n\n***Time Complexity :*** **`O(N)`**\n***Space Complexity :*** **`O(1)`** only constant extra space is being used.\n\n\n---\n\n\u2714\uFE0F ***Solution - V (Linear Search)***\n\nWe know that the given array is sorted and so duplicates occur adjacently. So, we can just iterate over the array and starting from the 1st element of array, we compare each one with its next adjacent element. If the next element is not equal, we know that current element has occured only once and thus return it as answer.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        for(int i = 0; i < size(nums)-1; i+=2) \n\t\t\tif(nums[i] != nums[i+1])\n                return nums[i];\n        return nums.back();\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        for i in range(0, len(nums)-1, 2):\n            if nums[i] != nums[i+1]:\n                return nums[i]\n        return nums[-1]\n```\n\n***Time Complexity :*** **`O(N)`**, for iterating array once.\n***Space Complexity :*** **`O(1)`** only constant extra space is being used.\n\n---\n\n\u2714\uFE0F ***Solution - VI (Binary Search)***\n\nThis approach uses the fact that since the array is sorted, every duplicate element occur adjacently. We can also see that the length of given array must be odd (Why? All element occur twice while only 1 element occurs once). \n\nLet the search range be `[L, R]`. Now, when we consider the mid element, the array is split into two equal halves on the left and right sides. Then we have following cases -\n1. `nums[mid] == nums[mid+1]`:\n\t* **Left Half Length = Right Half Length = Even :** In this case, we can be sure that our answer lies in the right half. How? One element of right half: `nums[mid+1]` matches with `nums[mid]`. So, leaving `nums[mid+1]` aside, we only have odd number of elements to pair up with each other in the right half. This means one element must be such that it cannot be paired with anyone and this is our required answer that occurs only once. So do **`L = mid+2`** (`+2` to skip `nums[mid]` and `nums[mid+1]` & keep search space odd for next iteration)\n\t* **Left Half Length = Right Half Length = Odd :** In this case, we can be sure that our answer lies in the left half. Again, how? Following same reasoning, one element of left half: `nums[mid+1]` matches with `nums[mid]`. So, leaving `nums[mid+1]` aside, the right half consists of even number of elements which can pair up with each other completely. However, left half only consists odd elements and thus one element which cannot be paired with anyone is our required answer. So do **`R = mid-1`** (`-1` to skip `nums[mid]` & keep search space odd for next iteration)\n\n2. `nums[mid] == nums[mid-1]`: We can follow similar reasoning based on array lengths as above -\n\t* **Left Half Length = Right Half Length = Even :** The answer lies in the left half. How? One element of left half: `nums[mid-1]` matches with `nums[mid]`. This leaves left half with odd number of elements to pair up with each other and one element that cant be paired with anyone is the required answer. So do **`R = mid-2`**\n\t* **Left Half Length = Right Half Length = Odd :** The answer lies in right half. How? One element of left half: `nums[mid-1]` matches with `nums[mid]`. This leaves left half with even number of elements which can pair up with each other completely. However, right half only consists odd elements and thus one element which cannot be paired with any other is the required answer. So do **`L = mid+1`**.\n\n3. If neither of above condition are satisfied, then we can be sure that `nums[mid]` itself is the required element occuring once (since it doesnt match with its neighbours). So we can just return it.\n\n```python\nnums = [1,2,2,3,3,4,4,8,8]\n\n1. [L = 0, R = 8] => mid = 4 and nums[mid] == nums[mid-1]\n   The left half length is even and 1 element is equal to nums[mid].\n   This tells us that left half is left with odd elements to pair up with each other\n   One element will be left out which is our answer. So search in left half - [0, 2]\n   We decremented R by 2 to keep remaining search space of odd length so we can repeat same process\n   \n2. [L = 0, R = 2] => mid = 1 and nums[mid] == nums[mid+1]\n   The left half is of odd length and one element cant be paired with another.\n   So our answer exist in left half. So search in left half - [0, 0]\n   \n3. [L = 0, R = 0] => mid = 1 and nums[mid] != nums[mid-1] and nums[mid] != nums[mid+1]\n   This means nums[mid] is our final answer since it is not equal to either of its neighbours\n```\n\nThe below code is a direct translation of above logic -\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = size(nums), L = 0, R = n-1, mid;\n        while(L <= R) {\n            mid = (L + R) >> 1;\n            bool isHalfEven = (mid-L) % 2 == 0;          // check length of each half is odd or even\n\t\t\t\n            if(mid+1 < n && nums[mid] == nums[mid+1])    // case: 1\n                if(isHalfEven) L = mid+2;\n                else R = mid-1;\n\t\t\t\t\n            else if(mid && nums[mid] == nums[mid-1])     // case: 2\n                if(isHalfEven) R = mid-2;\n                else L = mid+1;\n\t\t\t\t\n            else return nums[mid];                       // case: 3\n        }\n        return -1;   // wont be reached since we will always find required element inside loop\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        L, R, mid = 0, len(nums)-1, 0\n        while L <= R:\n            mid = (L + R) >> 1\n            isHalfEven = (mid-L) % 2 == 0\n            \n            if mid+1 < len(nums) and nums[mid] == nums[mid+1]:\n                if isHalfEven: L = mid + 2\n                else: R = mid - 1\n            elif mid and nums[mid] == nums[mid-1]:\n                if isHalfEven: R = mid - 2\n                else: L = mid + 1\n            else: \n                return nums[mid]\n```\n\n***Time Complexity :*** **`O(logN)`**, each time we are eliminating half of search space using binary search\n***Space Complexity :*** **`O(1)`** only constant extra space is being used.\n\n---\n\n\u2714\uFE0F ***Solution VII (Binary Search - 2nd Approach)***\n\nWe can apply binary search using slightly different logic as well. \n\nSuppose you are given a sorted array with all elements occur twice. For eg. `[1,1,2,2,5,5,7,7,8,8]`. So, here we can see that the elements follow the condition - **`nums[0] == nums[1], nums[2] == nums[3],..., nums[2*k] == nums[2*k+1]`**. Now, if we insert an element somewhere in the array, the above relation wont be satisfied from that point of insertion. Eg. `[1,1,2,2,4,5,5,7,7,8,8]` the condition starts to fail from element `4`, that is from point where single-occurence element is present.\n\nThus, we can use this observation to apply binary-search to find the starting point from where the above condition starts to fail. This start point is the index of element occuring once. The binary search will be applied as follows -\n\n1. Initialize the search space as `[L, R] = [0, n-1]` and repeat the following step till `L <= R`.\n2. Find the `mid` position and check if the above condition **`nums[2*k] == nums[2*k+1]`** is satisifed or not. \nFor this, firstly we must ensure that `mid` is even. If `mid` is odd, decrease it by 1 to make it even. \nThen, we need to check if the condition is satisfied or not - \n\t* **`nums[mid] == nums[mid+1]` :** The condition is correctly satisfied till index `mid+1`. So, the required element must occur somewhere on the right of `mid+1`. So do `L = mid+2`.\n\t* **`nums[mid] != nums[mid+1]` :** The condition is not satisfied at this point. So, the required element must either be `nums[mid]` or occur somewhere on the left of `mid` due to which the relation is not satisfied. Mark `nums[mid]` as a potential answer and search if condition is satisfied to the left of `mid` by doing `R = mid-1`\n\nFinally, we return the `ans` which was marked as potential answer during the binary search. \n\n```python\nnums = [1,1,2,2,3,3,4,4,5,5,6]\n\n1. [L = 0, R = 10] => mid = 5\n    Since mid is odd. We subtract 1 and mid becomes 4. Now, nums[mid] == nums[mid+1]\n   So condition is satisfied upto this point.\n   So the answer exists in right half in the [mid+2, R] = [6, 10] range\n   \n2. [L = 6, R = 10] => mid = 8 and nums[mid] == nums[mid+1]\n   Again, condition is satisfied upto this point\n   So, answer must exist in the right half in [mid+2, R] = [10, 10]\n   \n3. [L = 10, R = 10] => mid = 10\n   Now, mid+1 >= n and so we get nums[mid] != nums[mid+1]\n   So the condtion fails here. So mid is a potential answer. \n   We mark nums[mid] as ans and search in [L, mid-1] = [10, 9] range\n   \n   But since L > R, we break out of loop,\n   We finally return the marked answer which is nums[10] = 6\n```\n\n\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = size(nums), L = 0, R = n-1, mid, ans;\n        while(L <= R) {\n            mid = (L + R) >> 1;\n            if(mid & 1) mid--;                              // make mid even to check for required condition\n            if(mid+1 < n && nums[mid] == nums[mid+1])       // condition satisfied upto mid+1:\n                L = mid+2;                                  // so search in [mid+2, R] to find point where condition starts to fail\n            else                                            // condition not satisfied:\n                R = mid-1, ans = nums[mid];                 // nums[mid] is potential answer. search [L, mid-1] to see if condition started to fail somewhere before\n        }\n        return ans;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        L, R, mid, ans = 0, len(nums)-1, 0, 0\n        while L <= R:\n            mid = ((L + R) >> 2) << 1  # Does the same thing as above, i.e, ensuring mid is even\n            if mid+1 < len(nums) and nums[mid] == nums[mid+1]:\n                L = mid + 2\n            else: \n                R, ans = mid - 1, nums[mid]\n        return ans\n```\n\nOr instead of the usual way of declaring `[L,R]` as extremes of binary search space and searching within it, we can make a slight change to make the code a bit more concise (and also directly apply condition of `nums[2*k]==nums[2*k+1]`):\n\n**C++**\n\n```cpp\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {;\n        int L = 0, R = size(nums) / 2, mid;\n        while(L < R){\n            mid = (L + R) >> 1;\n            if(nums[2*mid] == nums[2*mid + 1])\n                L = mid + 1;\n            else\n                R = mid;\n        }\n        return nums[2 * R];\n    }\n};\n```\n\n***Time Complexity :*** **`O(logN)`**, each time we are eliminating half of search space using binary search\n***Space Complexity :*** **`O(1)`**\n\n---\n\n\uD83D\uDCA1 **Note :**\n* If you observe both binary search approaches carefully, you can see that it wouldn\'t have mattered if the array was unsorted. The only thing we required to apply binary search is that the duplicate elements occur adjacent to each other. \n\tSo the above **Binary-Search approach works for both sorted & un-sorted arrays given that duplicates occur adjacently.**\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]