algoadvance

136. Single Number

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

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

Constraints:

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
Each element in the array appears twice except for one element which appears only once.

Can we assume the input list is always valid and adheres to the given constraints?
- Yes, you can assume that the input list always adheres to the given constraints.
Is there any constraint related to memory usage or performance we need to be mindful of?
- The output should be efficient in terms of time complexity. Aim for linear time complexity with constant space complexity if possible.

To solve this problem efficiently, we can leverage the properties of the XOR bitwise operation:

XOR Properties:
- a ^ a = 0 (XOR of a number with itself is 0)
- a ^ 0 = a (XOR of a number with 0 is the number itself)
- XOR is commutative and associative.
Observations:
- Since XOR of two same numbers is 0, XORing all numbers in the array will cancel out all the numbers that appear twice, leaving the number that appears once.

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Initialize a variable result to 0.
Iterate through each number in the nums array.
For each number, perform XOR operation with result (i.e., result ^= num).
After processing all numbers, result will contain the single number that appears only once.

Time Complexity: O(n), where n is the number of elements in the nums array. We are iterating through each element exactly once.
Space Complexity: O(1), constant space. We are using only a single extra variable (result) regardless of the input size.

This approach ensures both optimal time and space performance.