Single Number

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

Example 3:

Input: nums = [1]

Output: 1

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

Approach: XOR Bit Manipulation (Optimal Solution)

Algorithm

1. Initialize a variable result = 0
2. XOR every element of the array with result
3. Pairs cancel out (x XOR x = 0), leaving only the single number

Time & Space Complexity

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - only one variable is used

Java Implementation

public class SingleNumber {

    /**
     * Find the element that appears only once.
     * @param nums Array where every element appears twice except one
     * @return The single element
     */
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {2, 2, 1};
        System.out.println("Input: nums = [2, 2, 1]");
        System.out.println("Output: " + singleNumber(nums1)); // Expected: 1

        int[] nums2 = {4, 1, 2, 1, 2};
        System.out.println("Input: nums = [4, 1, 2, 1, 2]");
        System.out.println("Output: " + singleNumber(nums2)); // Expected: 4

        int[] nums3 = {1};
        System.out.println("Input: nums = [1]");
        System.out.println("Output: " + singleNumber(nums3)); // Expected: 1
    }
}

Example Walkthrough

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

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

Answer: 4.

Key Points

1. Self-Inverse Property: x XOR x = 0 and x XOR 0 = x
2. Commutative & Associative: Order does not matter, pairs always cancel
3. Constant Space: Meets the O(1) space requirement
4. Linear Time: Meets the O(n) runtime requirement
5. Negative Numbers Work Too: XOR operates on bit patterns directly