Solution For Single Number

Problem Statement:

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

Approach:

The given problem can be solved by using the XOR operator.

XOR operator, also known as the exclusive or operator, is a bit-wise operator that takes two binary numbers and performs the logical XOR operation on each pair of corresponding bits. The result of this operation is a binary number where each bit represents whether the corresponding bits of the two operands differ.

XOR can be used to determine which bits are different between two binary numbers. When you XOR two binary numbers, the resulting bits are 1 when the corresponding bits of the two operands differ; otherwise, the resulting bits are 0.

If nums=[2,2,1], as 2^2=0 and 0^1=1, the expression evaluates to 1, which is the required output.

If nums=[4,1,2,1,2], as 4⊕1⊕2⊕1⊕2=(4⊕2)⊕1⊕1⊕2=0⊕2⊕2=0⊕0=0, the expression evaluates to 4 which is the required output.

Algorithm:

1. Initialize a variable called ‘output’ with 0.
2. Loop through each element in the array.
3. For each element, use the XOR operator to XOR it with the current value of ‘output’.
4. Update the value of ‘output’ with the result of the XOR operation.
5. After looping through all the elements, the final value of ‘output’ will be the single number that appears only once in the array.

Pseudo Code:

function singleNumber(nums):
output = 0
for num in nums:
output = output ^ num
return output

Complexity Analysis:

Time complexity: O(n). We are looping through each element in the array once.

Space complexity: O(1). We are using only constant extra space.

Code:

class Solution:
def singleNumber(self, nums: List[int]) -> int:
output = 0
for num in nums:
output = output ^ num
return output

This solution has been accepted by LeetCode and passes all test cases.

Step by Step Implementation For Single Number

class Solution {
    public int singleNumber(int[] nums) {
        // create a hashmap to store the number of times each element appears in the array
        HashMap map = new HashMap();
        
        // iterate through the array and store the number of times each element appears in the hashmap
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        
        // iterate through the hashmap and return the element that appears only once
        for (int key : map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        
        // if no element appears only once, return -1
        return -1;
    }
}

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # create a hashmap to store the number of occurrences of each number
        num_occurrences = {}
        
        # iterate through the list of numbers
        for num in nums:
            # if the number is not in the hashmap, add it and set its value to 1
            if num not in num_occurrences:
                num_occurrences[num] = 1
            # if the number is already in the hashmap, increment its value by 1
            else:
                num_occurrences[num] += 1
        
        # iterate through the hashmap
        for num, occurrences in num_occurrences.items():
            # if the number of occurrences is 1, return that number
            if occurrences == 1:
                return num

var singleNumber = function(nums) {
    // create hashmap to store values
    const hashmap = {};
    
    // iterate through array and store values in hashmap
    for (let i = 0; i < nums.length; i++) {
        if (hashmap[nums[i]]) {
            // if value is already in hashmap, delete it
            delete hashmap[nums[i]];
        } else {
            // if value is not in hashmap, store it
            hashmap[nums[i]] = true;
        }
    }
    
    // return the only remaining value in hashmap
    return Object.keys(hashmap)[0];
};

class Solution {
public:
    int singleNumber(vector& nums) {
        int result = 0;
        for(int i = 0; i < nums.size(); i++) {
            result ^= nums[i];
        }
        return result;
    }
};

public class Solution {
    public int SingleNumber(int[] nums) {
        // create a hashset to store all the unique numbers
        HashSet set = new HashSet();
        
        // loop through the array
        for(int i = 0; i < nums.Length; i++)
        {
            // if the number is not in the hashset, add it
            if(!set.Contains(nums[i]))
            {
                set.Add(nums[i]);
            }
            // if the number is already in the hashset, remove it
            else
            {
                set.Remove(nums[i]);
            }
        }
        
        // return the only remaining number in the hashset, which is the single number
        return set.First();
    }
}