Single Number easy

Problem Statement

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

Steps to Solve

The core idea is to leverage the bitwise XOR operator (^). The XOR operator has the following properties:

  • Commutative: a ^ b = b ^ a
  • Associative: a ^ (b ^ c) = (a ^ b) ^ c
  • Identity element: a ^ 0 = a
  • Inverse element: a ^ a = 0

Using these properties, we can XOR all the numbers in the array. Since a ^ a = 0, all the numbers that appear twice will cancel each other out, leaving only the single number.

Explanation

Let's trace Example 2 ([4,1,2,1,2]) through the XOR operation:

  1. Start with 0.
  2. 0 ^ 4 = 4
  3. 4 ^ 1 = 5
  4. 5 ^ 2 = 7
  5. 7 ^ 1 = 6
  6. 6 ^ 2 = 4

The final result is 4, which is the single number.

Code (C++)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num; 
        }
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n), where n is the number of elements in the array. We iterate through the array once.
  • Space Complexity: O(1). We only use a constant amount of extra space to store the result variable. This satisfies the problem's constraint of using constant extra space.