LeetCode #136 Single Number

Posted on Edited on In Disqus:

Description: https://leetcode.com/problems/single-number/description/
Solution: https://leetcode.com/problems/single-number/solution/
Difficulty: Easy

The difficulty of the problem lies in this requirement: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

I thought hard for a long time but still could not satisfy both O(n) time complexity and O(1) space complexity. I went to read the solution, and Approach 4 meets the requirement. It uses the properties of the XOR bit operation, which really is a bit of a trick. You can also see the comment section full of exclamations like “awesome.” Once you know it, it is not hard; the next time I encounter it, it will be Easy.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ret = 0
        for i in nums:
            ret ^= i
            
        return ret