Single Number - Java Solution

1. Introduction

In this post, we address a common problem in array processing known as "Single Number." This problem is notable for its constraint of solving it with linear runtime complexity and using only constant extra space. The challenge is to find the unique element in an array where every other element appears twice.

Problem

Given a non-empty array of integers nums, where every element appears twice except for one, the task is to find that single element. The solution must be implemented with O(n) time complexity and O(1) space complexity.

Examples:

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

Output: 1

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

Output: 4

- Input: nums = [1]

Output: 1

2. Solution Steps

1. Initialize a variable singleNumber with 0.

2. Iterate through the array nums.

3. Apply the XOR operation between singleNumber and each element in the array.

4. Since XOR of a number with itself is 0 and the XOR of a number with 0 is the number itself, the result will be the unique number.

3. Code Program

public class SingleNumber {
    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 1, 2};
        System.out.println(findSingleNumber(nums)); // Test the function
    }

    // Function to find the single number in the array
    public static int findSingleNumber(int[] nums) {
        int singleNumber = 0;

        for (int num : nums) {
            singleNumber ^= num;
        }

        return singleNumber;
    }
}

Output:

4

Explanation:

1. findSingleNumber: This function identifies the unique element in nums.

2. It initializes singleNumber to 0 and iterates through the array.

3. The function employs the XOR operation, which cancels out duplicate numbers (as n XOR n = 0 and n XOR 0 = n).

4. Thus, after processing the entire array, singleNumber holds the unique element.

5. This approach is efficient, ensuring linear time complexity (O(n)) and constant space complexity (O(1)).

6. It effectively leverages the properties of the XOR operation to isolate the single occurrence element in a simple and elegant way.