13. Single Number

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.

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

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

Input: nums = [1]
Output: 1

Problem Breakdown:

1. The key insight is using XOR (exclusive or). XOR has two important properties: a ^ a = 0 (any number XOR itself is 0) and a ^ 0 = a (any number XOR 0 is itself).

• # XOR properties:
  # a ^ a = 0
  # a ^ 0 = a
  # XOR is commutative and associative

2. Initialize a result variable to 0. We will XOR every number in the array with this result.

• result = 0

3. Iterate through all numbers and XOR each one with result. All paired numbers cancel out (become 0), leaving only the single number.

• for num in nums:
      result ^= num

4. After processing all numbers, result holds the single number that appeared only once.

• return result

Summary:

XOR all numbers together. Since XOR of a number with itself is 0, and XOR of a number with 0 is itself, all duplicate pairs cancel out, leaving only the unique number. This achieves O(1) space with O(n) time.

Time and Space Complexity:

Time Complexity: O(n) - we iterate through the array once.

Space Complexity: O(1) - we only use one variable.

Python Solution:

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

JavaScript Solution:

var singleNumber = function(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
};

Java Solution:

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}