Single Number Explained

Problem Statement

Given a non-empty array of integers nums, every element appears exactly twice except for one element that appears only once. Your task is to find that single number. The solution must run in O(n) time complexity and use O(1) extra space, making bitwise XOR an ideal approach since it cancels out paired numbers while preserving the unique one.

Example

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

Output: 4

Explanation: The numbers 1 and 2 each appear twice, while 4 appears only once.

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4, 1, 2, 1, 2};
        System.out.println(sol.singleNumber(nums)); // 4
    }
}
            

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

# Example usage
print(single_number([4, 1, 2, 1, 2]))  # 4
            

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

// Example usage
console.log(singleNumber([4, 1, 2, 1, 2])); // 4
            

Explanation

• Initialize a variable result to 0 to store the XOR of all numbers.
• Iterate through the array, performing XOR between result and each number.
• XOR has the property that a ^ a = 0 and a ^ 0 = a.
• All paired numbers cancel out (become 0), leaving only the single number.
• Return the final value of result.

Note