Problem

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Examples

Example 1:

1
2

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

Solution

Method 1 - Naive Approach

Use nested for loops and compare each element with all other elements and return the element which appears only once. Time Complexity: O(n^2)

Method 2 - Using Hashset

Very common method.

Method 3 - Sorting and Keeping Count

We can sort the array and compare adjacent elements. Sorting for integers take O(n) time if we use counting or bucketsort. So, it can be overall O(n). (If we use comparison based sorts, then it will be O(nlog n))

Method 4 - Using Xor 🏆

This method is slightly less intuitive and is similar to Single Number. We will take 3 variables - ones, twos and threes. ones will store result of xor from element which occurs once. twos will store the store and bits for elements which occur twice and threes will contain and(&) between ones and twos.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int singleNumber(int[] A) {
	int ones = 0, twos = 0, threes = 0;
	for (int i = 0; i<A.length; i++) {
		twos |= ones & A[i];
		ones ^= A[i];
		threes = ones & twos;
		ones &= ~threes;
		twos &= ~threes;
	}
	return ones;
}

Complexity

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

Method 5 - Using Bit Vector and Divisibility by 3 🏆

We know that for number 1…n, we have all numbers except one which occur thrice. Hence, all the bits will be divisible by 3, except for the bits of that number. And that is our answer.

For eg.

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

Say arr[] = {6, 6, 6, 3}

1 1 0
1 1 0
1 1 0
0 1 1
__________+
3 4 1
__________mod 3
0 1 1

Now modulus with 3 is 011 = 3 -> element occuring only once

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int singleNumber(int[] nums) {
	int[] bitVector = new int[32];
	int ans = 0;
	for (int i = 0; i < 32; i++) {
		for (int num: nums) {
			bitVector[i] += (num >> i) & 1;
		}
		ans |= (bitVector[i] % 3) << i;
	}
	return ans;
}
1
2
3
4
5

Space complexity - `O(32) = O(1)`

We don't need to save even this 32 bit array, as we can focus on current bit and solve the `ans`.

###### Code with Single Integer as Bit Vector Array
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int singleNumber(int[] nums) {
	int ans = 0;
	for (int i = 0; i < 32; i++) {
		int bitVector = 0; // reset i'th bit
		for (int num: nums) {
			bitVector += (num >> i) & 1;
		}
		ans |= (bitVector % 3) << i;
	}
	return ans;
}

Complexity

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

Dry Run

Suppose, nums = [2, 2, 2, 13]. First, let’s look at the binary representation of these numbers (32-bit representation):

1
2
3
4

 2:  0000 0000 0000 0000 0000 0000 0000 0010
 2:  0000 0000 0000 0000 0000 0000 0000 0010
 2:  0000 0000 0000 0000 0000 0000 0000 0010
 13: 0000 0000 0000 0000 0000 0000 0000 1101

  • For i = 0 (checking least significant bit):

    1
2
3
4
5
6
7
8
9

     bitVector = 0
 num = 2 => (2 >> 0) & 1 = (10 >> 0) & 1 = 0
 num = 2 => (2 >> 0) & 1 = (10 >> 0) & 1 = 0
 num = 2 => (2 >> 0) & 1 = (10 >> 0) & 1 = 0
 num = 13 => (13 >> 0) & 1 = (1101 >> 0) & 1 = 1

 bitVector after the loop = 0 + 0 + 0 + 1 = 1
 Since 1 % 3 = 1, the least significant bit of `ans` is set to 1.
 ans |= (1 % 3) << 0 => ans |= 1 => ans = 0001 (in binary)

  • For i = 1 (checking the second least significant bit):

    1
2
3
4
5
6
7
8
9

     bitVector = 0
 num = 2 => (2 >> 1) & 1 = (10 >> 1) & 1 = 1 & 1 = 1
 num = 2 => (2 >> 1) & 1 = (10 >> 1) & 1 = 1 & 1 = 1
 num = 2 => (2 >> 1) & 1 = (10 >> 1) & 1 = 1 & 1 = 1
 num = 13 => (13 >> 1) & 1 = (1101 >> 1) & 1 = 110 & 1 = 0

 bitVector after the loop = 1 + 1 + 1 + 0 = 3
 Because 3 % 3 = 0, the second bit of `ans` remains unset.
 ans |= (3 % 3) << 1 => ans |= 0 => ans remains 0001

  • For i = 2 (checking the third least significant bit):

    1
2
3
4
5
6
7
8
9

     bitVector = 0
 num = 2 => (2 >> 2) & 1 = (10 >> 2) & 1 = 0 & 1 = 0
 num = 2 => (2 >> 2) & 1 = (10 >> 2) & 1 = 0 & 1 = 0
 num = 2 => (2 >> 2) & 1 = (10 >> 2) & 1 = 0 & 1 = 0
 num = 13 => (13 >> 2) & 1 = (1101 >> 2) & 1 = 11 & 1 = 1

 bitVector after the loop = 0 + 0 + 0 + 1 = 1
 Since 1 % 3 = 1, the third significant bit of `ans` is set to 1.
 ans |= (1 % 3) << 2 => ans |= 4 => ans = 0101 (in binary)

  • For i = 3 (checking the third least significant bit):

    1
2
3
4
5
6
7
8
9

     bitVector = 0
 num = 2 => (2 >> 3) & 1 = (10 >> 2) & 1 = 0 & 1 = 0
 num = 2 => (2 >> 3) & 1 = (10 >> 2) & 1 = 0 & 1 = 0
 num = 2 => (2 >> 3) & 1 = (10 >> 2) & 1 = 0 & 1 = 0
 num = 13 => (13 >> 3) & 1 = (1101 >> 3) & 1 = 1 & 1 = 1

 bitVector after the loop = 0 + 0 + 0 + 1 = 1
 Since 1 % 3 = 1, the third significant bit of `ans` is set to 1.
 ans |= (1 % 3) << 3 => ans |= 4 => ans = 1101 (in binary)