Single Number

Solution

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

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

 

Explaination

 

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        int result = 0;
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        
        for (Integer key : map.keySet()) {
            if (map.get(key) == 1) {
                result = key;
            }
        }
        return result;
    }
}

 

Map

If the the length of nums array is 1, return nums[0] index.

Otherwise HashMap is initialized to store the frequency of each element in the nums array.  and put all elements of the nums in the map using a for loop. If the element is already stored in the map as a key, the value is incremented.

Lastly, find the value 1 whose key occurs only one time using a for loop and return the result.

 

Problem

Space Complexity: The requirement of the problem is to solve it using constant extra space (O(1) space), but this solution uses extra space proportional to the size of the input array (O(n)), due to the HashMap.

 

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for(int i=0; i<nums.length; i++) {
            single^=nums[i];
        }
        return single;
    }
}

 

XOR

The XOR operator cancels out numbers that appear in pairs. This is because any number XORed with itself becomes 0 (a ^ a = 0), and any number XORed with 0 remains unchanged (a ^ 0 = a).

 

If the nums is [1, 2, 1, 2, 4], (1^1) ^(2^2)^(4) = 4.

 

XOR operation eliminates pairs of identical numbers, leaving only the number that appears once. This solution has both O(n) time complexity and O(1) space complexity, which meets the problem's constraints.