[LeetCode] 136. Single Number

1. Question

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1
Example 2:

Input: nums = [4,1,2,1,2]
Output: 4
Example 3:

Input: nums = [1]
Output: 1

2. Thoughts

Use Bit manipulation.

3. Tips learned

3.1. Bit manipulation

Learned from: https://velog.io/@hojin11choi/TIL-Python-Bit-manipulation

4. My solution

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for num in nums:
            ans ^= num
        return ans

61/61 cases passed (107 ms)
Your runtime beats 92.88 % of python3 submissions
Your memory usage beats 20.35 % of python3 submissions (19.9 MB)

5. AI Solution and Improvements

Your solution for finding the single number in an array where every other element appears twice is both correct and efficient. You've used the bitwise XOR (^) operation, which is a clever and optimal way to solve this problem with a linear runtime complexity (O(n)) and constant extra space (O(1)).

Let's explain how your solution works:

1. Bitwise XOR Operation (^):

   • The XOR operation has a unique property: for any number x, x ^ x = 0, and x ^ 0 = x.
   • This means if you XOR a number with itself, the result is 0, and if you XOR 0 with a number, you get the number back.
   • Additionally, XOR is commutative and associative, which means the order in which you apply XOR to a set of numbers doesn't change the result.

2. Using XOR to Find the Single Number:

   • In your problem, every element except one appears twice in the array.
   • As you iterate through the array and XOR all the numbers (ans ^= num), every number that appears twice will effectively cancel itself out (because x ^ x = 0).
   • The single number that doesn't have a pair will not be cancelled out and will be the final result after the XOR of all elements.
   • For example, in [4,1,2,1,2], the operations are essentially (4^1^2^1^2). Both 1's and 2's cancel themselves out, leaving 4 as the result.

3. Your Implementation:

   • You initialize ans to 0. This is important because XOR-ing any number with 0 gives the number itself.
   • You then iterate through each number in the array, continuously XOR-ing it with ans.
   • By the end of the loop, ans contains the single number that does not have a duplicate in the array.

In conclusion, your approach efficiently solves the problem in the required constraints of linear time complexity and constant space complexity. It's an excellent example of the power of bitwise operations in certain algorithmic problems.