Single Number 1 - All elements except one occur twice

Problem

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.

OR

Given an array of integers where every element appears exactly twice except for one element which appears only once, find that unique element.

Follow-up:

Given an array of integers where every element occurs an even number of times except one element which occurs an odd number of times, find that element.

Examples

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

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/b6Oy8R4uNGY" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Using Hash-set

The question now is do you know any other ways to do this?

Code

Java

class Solution {
	public int singleNumber(int[] nums) {
		HashSet<Integer> set = new HashSet<Integer> ();
		for (int n: nums) {
			if (!set.add(n)) {
				set.remove(n);
			}
		}
		Iterator<Integer> it = set.iterator();
		return it.next();
	}
}

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num_set = set()
        for n in nums:
            if n not in num_set:
                num_set.add(n)
            else:
                num_set.remove(n)
        
        # Since there's only one element left, we can return it
        return num_set.pop()

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)

Method 2 - Using Sorting

Code

Java

class Solution {
	public int singleNumber(int[] nums) {
		// Sort the array
		Arrays.sort(nums);
		int n = nums.length;
	
		for(int i=0; i < n - 1; i = i + 2) {
			// compare num[i] with nums[i+1]
			// If nums[i] not equal to nums[i+1]
			// nums[i] is the number which occured only once
			if(nums[i] != nums[i+1]) {
				return nums[i];
			}
		}
		// As i = n-1 and no element left to compare, so this is the single number 
	   return nums[n-1];
	}
}

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Sort the array
        nums.sort()
        n = len(nums)
        
        # Iterate through the sorted array in steps of 2
        for i in range(0, n - 1, 2):
            # Compare nums[i] with nums[i + 1]
            # If they are not equal, nums[i] is the single number
            if nums[i] != nums[i + 1]:
                return nums[i]
        
        # If no mismatch found in pairs, the last element is the single number
        return nums[n - 1]

Complexity

• ⏰ Time complexity: O(n log n)
• 🧺 Space complexity: O(1)

Method 3 - Using XOR 🏆

The key to solve this problem is bit manipulation. XOR will return 1 only on two different bits. So if two numbers are the same, XOR will return 0. Finally only one number left.

This approach also solves the follow-up

If every element occurs an even number of times except one (which occurs an odd number of times), XOR-ing all elements will leave the odd-occurring element. This is because all even-count elements cancel out, leaving only the one with odd frequency.

Code

Java

class Solution {
	public int singleNumber(int[] nums) {
		int ans = 0;
		for (int num: nums) {
			ans = ans ^ num;
		}
		return ans;
	}
}

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Initialize ans as 0
        ans = 0
        
        # Iterate through each number in the array
        for num in nums:
            # XOR the current number with ans
            ans = ans ^ num
        
        # Return the result
        return ans

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)