Question:
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.
Add On: You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,3,2] Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99] Output: 99
Constraints:
- 1 <= nums.length <= 3 * 104
- -231 <= nums[i] <= 231 - 1
- Each element in nums appears exactly three times except for one element which appears once.
You can find the question here.
Solution:
So, I was going through some coding problems and stuck with this one for quite some time, and after a ton of research on google, going through different posts and portals, I have understood this problem. Will try to explain it as simply as I can.
The problem has 3 solutions:
- Using HashMap: But as we know that will add O(N) space complexity and we don't want that. But for a little bit of understanding, the approach is to iterate the array, get the count of the digits and maintain it in a map. Then iterate the map and where the count is 1 that will be your answer.
- Using Bitwise operators: The logic for this approach is to think of the numbers in bits and then add all the bits of each position. So after adding you will see that the sum is either multiple of 3 or a multiple of 3 + 1 (Because the other number is occurring once only). After this, if you do a modulo on this sum you will have the result. You will understand better with the example.
Example: Array - [5, 5, 5, 6]
- 5 represented in bits: 101
- 6 represented in bits: 110
- [ 101, 101, 101, 110] (Binary Representation of values)
- After adding to particular positions, we will have : 0th -> 3, 1th -> 1, 2nd -> 4
- And if we mod by 3 it will become: 0th -> 0, 1th -> 1, 2nd -> 1
- Which in decimal representation is our answer 6.
- Now we need to code the same. I have explained the code using comments.
public class SingleNumberII {
/*
* Because the max integer value will go upto 32 bits
* */
private static final int INT_SIZE = 32;
public int singleNumber(final int[] A) {
int result = 0;
for(int bitIterator = 0; bitIterator < INT_SIZE; bitIterator++) {
int sum = 0, mask = (1 << bitIterator);
/*
* Mask:
* 1 << any number means -> it will add that number of 0 in right of 1
* 1 << 2 -> 100
* Why we need mask? So when we do addition we will only count 1's,
* this mask will help us do that
* */
for(int arrIterator = 0; arrIterator < A.length; arrIterator++) {
/*
* The next line is to do the sum.
* So 1 & 1 -> 0
* 1 & 0 -> 0
* The if statement will add only when there is 1 present at the position
* */
if((A[arrIterator] & mask) != 0) {
sum++;
}
}
/*
* So if there were 3 1's and 1 0's
* the result will become 0
* */
if(sum % 3 == 1) {
result |= mask;
}
}
/*So if we dry run our code with the above example
* bitIterator = 0; result = 0; mask = 1;
* after for loop the sum at position 0 will became 3. The if
* condition will be true for 5 as - (101 & 001 -> 001) and false for 6
* (110 & 001 -> 000)
* result -> 0 | 1 -> 0
*
* bitIterator = 1; result = 0; mask = 10;
* after for loop the sum at position 1 will became 1. The if
* condition will be true for 6 as - (110 & 010 -> 010) and false for 5
* (101 & 010 -> 000)
* result -> 00 | 10 -> 10
*
* bitIterator = 2; result = 10; mask = 100;
* after for loop the sum at position 2 will became 4. The if
* condition will be true for 6 as - (110 & 100 -> 100) and true for 5
* (101 & 100 -> 100)
* result -> 10 | 100 -> 110 (answer)
* */
return result;
}
As we can see this is not the best solution because we are unnecessarily iterating it over 32 times and it is also not that generalized. Which makes us visit our next approach.
- Using Bitwise operators (Optimized and Generalized): So for this approach, I'll try to explain the approach, then code it, and then how to make it generalize. We will take 2 flags(one and two) for analogy, consider them as Sets. So we the number appears 1st time it will be added in one only if it is not present in two. and we will do the same for two, meaning if the number appears 2nd time we will remove it from 1 and then add it to two(only if it is not present in one), and for the number appearing a third time it will be removed from the set two and will no longer exist in either set. You might have the question that why 2 sets(or variables) reason is explained in the next point.
public int singleNumberOptimized(int[] A) {
int one = 0, two = 0;
/*
* Two sets to maintain the count the number has appeared
* one -> 1 time
* two -> 2 time
* three -> not in any set
* */
for(int arrIterator = 0; arrIterator < A.length; arrIterator++){
/*
* IF one has a number already remove it, and it does not have that number
* appeared previously and it is not there in 2 then add it in one.
* */
one = (one ^ A[arrIterator]) & ~two;
/*
* IF two has a number already remove it, and it does not have that number
* appeared previously and it is not there in 1 then add it in two.
* */
two = (two ^ A[arrIterator]) & ~one;
}
/*
* Dry run
* First Appearance : one will have two will not
* Second Appearance : one will remove and two will add
* Third Appearance: one will not able to add as it is there in two
* and two will remove because it was there.
*
* So one will have only which has occurred once and two will not have anything
* */
return one;
}
How do we solve these types of questions more generically? The number of sets you need to create depends on the value of k (Appearance of every other integer). m >= log(K). (To count the number of 1's in the array such that whenever the counted number of 1 reaches a certain value, say k, the count returns to zero and starts over. To keep track of how many 1's we have encountered so far, we need a counter. Suppose the counter has m bits.) m will be the number of sets we need. For everything else, we are using the same logic. But wait what should I return, the logic is to do OR operations with all the sets which will eventually the OR operation on the single number with itself and some 0s, which interns to the single number. For a better understanding of this particular part go through this post here. I have tried my best to explain to you the solution. Hope you like it.
#HappyCoding