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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

Input: nums = [1]
Output: 1

Solution

Video explanation

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

Method 1 - Using Hash-set

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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();
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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.

Code

1
2
3
4
5
6
7
8
9

class Solution {
	public int singleNumber(int[] nums) {
		int ans = 0;
		for (int num: nums) {
			ans = ans ^ num;
		}
		return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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)