Problem

Given an array of integers, every element appears twice except for one. Find that single one.

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

Method 1 - Using Hash-set

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();
}

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

Complexity

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

Method 2 - Using Sorting

public int getSingleNumber(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];
}

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.

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

Complexity

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