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. Understanding the Problem: The core idea is to find the number that appears only once in the array, while all other numbers appear twice. We need an efficient algorithm that avoids nested loops (to maintain linear time complexity) and doesn't use significant extra space (constant space).

2. Using XOR: The XOR (exclusive OR) operation has a crucial property: x ^ x == 0 and x ^ 0 == x. This means that if we XOR a number with itself, the result is 0. If we XOR a number with 0, the result is the number itself.

3. Applying XOR to the Array: We can iterate through the array and perform XOR operations cumulatively. Because of the XOR property, numbers that appear twice will cancel each other out (resulting in 0), leaving only the single number.

4. Implementation: We initialize a variable result to 0. Then, we iterate through the array, XORing each element with result. The final value of result will be the single number.

Explanation

The XOR operation's properties allow us to efficiently solve this problem. Each pair of duplicate numbers will cancel each other out during the XOR operations. The number that's not duplicated will remain as the final result because XORing it with 0 (the initial value of result) yields the number itself.

Code

function singleNumber(nums: number[]): number {
    let result: number = 0;
    for (let i = 0; i < nums.length; i++) {
        result ^= nums[i]; // XOR operation
    }
    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.