Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Input: [2, 2, 1]
Input: [4, 1, 2, 1, 2]
from typing import List class Solution: def singleNumber(self, nums: List[int]) -> int: result = 0 for i in range(len(nums)): result ^= nums[i] return result
test = Solution() answer = test.singleNumber([1,1,2,4,2,3,3]) assert answer == 4 answer = test.singleNumber() assert answer == 1 print('All Passed!')
Big O Analysis
Space Complexity: O(1)
Time Complexity: O(N)