Single Number [LeetCode Top Interview Questions Series]

The basic idea is that the XOR of two equal numbers is 0, and the XOR of a number and 0 is the number itself. So, if we XOR all the numbers in the array, the duplicates will cancel each other out, and the result will be the single number that appears only once.

Here’s an example implementation in Java:

public class Test {

    public static void main(String[] args) {
        int[] nums = {4,1,2,1,2};
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        System.out.println(result);
    }
}

In this implementation, we start with result equal to 0, and then XOR each number in the array with result. Since the XOR of two equal numbers is 0, the duplicates will cancel each other out and result will be equal to the single number that appears only once.

The time complexity of this solution is O(n), where n is the number of elements in the input array nums, since we need to examine all the elements in the array. The space complexity is O(1), since we are only using a single variable result to store the result, and its size does not depend on the size of the input array.