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

  1. Utilize XOR Properties: The XOR operation (^) has a crucial property: a ^ a == 0 and a ^ 0 == a. This means XORing a number with itself results in zero, and XORing a number with zero results in the number itself.

  2. Iterate and XOR: We'll iterate through the input array nums. For each number, we'll XOR it with a running total (initialized to 0).

  3. Result: After iterating through the entire array, the running total will hold the single number that appeared only once. All the numbers that appeared twice will cancel each other out due to the XOR property.

Explanation

The solution leverages the bitwise XOR operator's properties to efficiently find the single number. Since a ^ a == 0, pairs of duplicate numbers will cancel each other out when XORed. The final result will be the unique number.

For example, in [4,1,2,1,2]:

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

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

Code

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = 0;
        foreach (int num in nums) {
            result ^= num;
        }
        return result;
    }
}

Complexity

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
  • Space Complexity: O(1). We use only a constant amount of extra space to store the result variable.