Best O(LogN) Solution
Approach 1\nXOR\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n\nclass Solution {\npublic:\n    int singleNonDuplicate(vector
# Approach 1\nXOR\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int ans = 0;\n        for (int i = 0; i < nums.size(); i++)\n            ans = ans ^ nums[i];\n        return ans; \n    }\n};\n```\n# Approach 2\nLinear Search\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size();\n        if (n == 1)\n            return nums[0];\n        for (int i = 1; i < n; i = i + 2)\n            if (nums[i - 1] != nums[i])\n                return nums[i - 1];\n        return nums[n - 1];    \n    }\n};\n```\n\n# Approach 3\nBinary Search\n\n# Complexity\n- Time complexity:\n$$O(logn)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size();\n        if (n == 1)\n            return nums[0];\n        if (nums[0] != nums[1])\n            return nums[0];    \n        int low = 0, high = n - 1;\n        while (low <= high) {\n            int mid = (low + high) / 2;\n            if ((nums[mid] != nums[mid - 1] || mid == 0) &&\n                (nums[mid] != nums[mid + 1] || mid == n - 1))\n                return nums[mid];\n             else if ((mid % 2 == 0 && nums[mid] == nums[mid - 1]) || \n                (mid % 2 == 1 && nums[mid] == nums[mid + 1])) \n                high = mid - 1;\n            else\n                low = mid + 1; \n        }\n        return -1;\n    }\n};\n```
['C++']