JavaScript | 96% | O(log n) time | O(1) space | Binary Search
\n\n# Approach\n\n### Linear search\n\nA \bigoplus A = 0 (XOR-ing a number with itself always equals zero)\nA \bigoplus 0 = A (XOR-ing a number with zero always
![image.png](https://assets.leetcode.com/users/images/f5d988de-7e19-4e38-b41e-73a2b04cc022_1676972922.5721262.png)\n\n# Approach\n\n### Linear search\n\n$$A \\bigoplus A = 0$$ ($$XOR$$-ing a number with itself always equals zero)\n$$A \\bigoplus 0 = A$$ ($$XOR$$-ing a number with zero always equals original number)\n\nIf we had an array where each element is present exactly twice, $$XOR$$-ing all elements together would equal zero (as per first rule).\nSince we have one element with no duplicate, $$XOR$$-ing it with the rest of the array would equal this element (as per second rule).\n\n```\nvar singleNonDuplicate = function(nums) {\n    let sum = 0;\n    \n    for (const num of nums) sum ^= num;\n    \n    return sum;\n};\n```\n\nOr, as a one-liner:\n\n```\nvar singleNonDuplicate = function(nums) {\n    return nums.reduce((acc, num) => acc ^ num, 0);\n};\n```\n\n### Binary search\n\nAssuming we already know how binary search works, the main question to answer is - **how to know when to move the pointer to the left or to the right**?\n\nLook at the array below, where each element has a duplicate.\n\n<table>\n    <tr>\n        <td style="background-color:#555;color:red">0</td>\n        <td style="color:red">0</td>\n        <td style="background-color:#555;color:orange">1</td>\n        <td style="color:orange">1</td>\n        <td style="background-color:#555;color:yellow">2</td>\n        <td style="color:yellow">2</td>\n        <td style="background-color:#555;color:green">3</td>\n        <td style="color:green">3</td>\n        <td style="background-color:#555;color:cyan">4</td>\n        <td style="color:cyan">4</td>\n    </tr>\n</table>\n\nYou can notice that every element at an odd index (grey background) is equal to the next element, and every element at an even index is equal to the previous element.\n\nIf we remove a single element from the left (such that there will be one element in the array with no duplicate), 0 in this case, the condition above would switch. Now, every element at an odd index (grey background) is equal to the previous element, and every element at an even index is equal to the next element.\n\n<table>\n    <tr>\n        <td style="background-color:#555;color:red">0</td>\n        <td style="color:orange">1</td>\n        <td style="background-color:#555;color:orange">1</td>\n        <td style="color:yellow">2</td>\n        <td style="background-color:#555;color:yellow">2</td>\n        <td style="color:green">3</td>\n        <td style="background-color:#555;color:green">3</td>\n        <td style="color:cyan">4</td>\n        <td style="background-color:#555;color:cyan">4</td>\n    </tr>\n</table>\n\nThis won\'t happen if we remove an element from the right, 4 in this case.\n\n<table>\n    <tr>\n        <td style="background-color:#555;color:red">0</td>\n        <td style="color:red">0</td>\n        <td style="background-color:#555;color:orange">1</td>\n        <td style="color:orange">1</td>\n        <td style="background-color:#555;color:yellow">2</td>\n        <td style="color:yellow">2</td>\n        <td style="background-color:#555;color:green">3</td>\n        <td style="color:green">3</td>\n        <td style="background-color:#555;color:cyan">4</td>\n    </tr>\n</table>\n\nWhat this means is, if we pick an arbitrary index in the array, and it matches the first condition, the single element must be on the right, otherwise, it\'s on the left, with one exception.\n\nIf the element does not equal the element on it\'s right, and neither the element on the left, we have found the element with no duplicate.\n\n```\nfunction singleNonDuplicate(nums) {\n    let left = 0;\n    let right = nums.length;\n    \n    while (left < right) {\n        let mid = (left + right) >>> 1;\n        if (mid % 2 !== 0) mid--;\n\n        const value = nums[mid];\n        \n        if (value !== nums[mid + 1] && \n            value !== nums[mid - 1]) {\n            return value;\n        }\n        \n        if (value === nums[mid - 1]) {\n            right = mid;\n        } else {\n            left = mid + 1;\n        }\n    }\n}\n```\n\n# Complexity\n- Time complexity: $$O(log n)$$\n\n- Space complexity: $$O(1)$$
['Math', 'Binary Search', 'JavaScript']