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:

The core idea to solve this problem efficiently leverages the bitwise XOR operator (^). The XOR operator has the following properties:

• x ^ 0 = x: XORing any number with 0 results in the number itself.
• x ^ x = 0: XORing a number with itself results in 0.
• x ^ y ^ x = y: XOR is associative and commutative.

We can use these properties to our advantage. If we XOR all the numbers in the array together, the numbers that appear twice will cancel each other out (because x ^ x = 0), leaving only the single number.

Explanation:

1. Initialization: We start with a variable result initialized to 0. This will accumulate the XOR result.
2. Iteration: We iterate through the nums array.
3. XOR Operation: In each iteration, we perform a bitwise XOR operation between the current element num and the current value of result. result = result ^ num;
4. Final Result: After iterating through the entire array, result will hold the value of the single number that appeared only once.

Code:

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : 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. This meets the problem's requirement of using only constant extra space.