Single Number II from leetcode

Question

The question about Single Number II from leetcode is:

Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Actually, I already found the solution from website, the solution is:

public int singleNumber(int[] A) {
    int one = 0, two = 0;
    for (int i = 0; i < A.length; i++) {
        int one_ = (one ^ A[i]) & ~two;
        int two_ = A[i] & one | ~A[i] & two;
        one = one_;
        two = two_;
    }
    return one;
}

However, I do not know why this code can work and actually I do not know the way of thinking of this problem when I first saw it? Any help. thx!

Solution 1

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 simple as I can.

The problem has 3 solutions:

1. 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 map. Then iterate the map and where the count is 1 that will be your answer.
2. Using Bitwise operators: The logic for this approach is to think 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 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 Reprenstation of values)
    After adding to particular positions, we will have
     0th -> 3, 1th -> 1,  2nd -> 4
    and if you 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 unnecessary iterating it over 32 times and it is also not that generalized. Which makes as to visit our next approach.

3. Using Bitwise operators (Optimized and Generalized):
   So for this approach, I'll try to explain the approach, then code and then how to make it generalize. We will take 2 flags(one, 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 4th 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;
}

4. How to solve these type 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

Solution 2

The idea is to reinterpret the numbers as vectors over GF(3). Each bit of the original number becomes a component of the vector. The important part is that for each vector v in a GF(3) vector space the summation v+v+v yields 0. Thus the sum over all vectors will leave the unique vector and cancel all others. Then the result is interpreted again as a number which is the desired single number.

Each component of a GF(3) vector may have the values 0, 1, 2 with addition being performed mod 3. The "one" captures the low bits and the "two" captures the high bits of the result. So although the algorithm looks complicated all that it does is "digitwise addition modulo 3 without carry".

Solution 3

Here is another solution.

   public class Solution {  
        public int singleNumber(int[] nums) {  
           int p = 0;  
           int q = 0;  
           for(int i = 0; i<nums.length; i++){  
              p = q & (p ^ nums[i]);  
              q = p | (q ^ nums[i]);  
           }  
           return q;  
        }  
    }  

Analysis from this blog post.

Solution 4

The code seems tricky and hard to understand at first glance. However, if you consider the problem in Boolean algebra form, everything becomes clear.

What we need to do is to store the number of 1's of every bit. Since each of the 32 bits follow the same rules, we just need to consider 1 bit. We know a number appears 3 times at most, so we need 2 bits to store that. Now we have 4 state, 00, 01, 10 and 11, but we only need 3 of them.

In your solution, 01 for one and 10 for two are chosen. Let one represents the first bit, two represents the second bit. Then we need to set rules for one_ and two_ so that they act as we hopes. The complete loop is 00->10->01->00(0->1->2->3/0).

It's better to make Karnaugh map a.k.a. K-map. For Karnaugh Map Ref.

3-state counter

Respective values of A[i], two, one and two_, one_ after

0 0 0 | 0 0
0 0 1 | 0 1
0 1 0 | 1 0
0 1 1 | X X
1 0 0 | 0 1
1 0 1 | 1 0
1 1 0 | 0 0
1 1 1 | X X

Here X denotes we don't care for that case or simply in the final value of two and one, wherever their output is 1, that can also be considered, the result will be same and 4th and 8th case won't exist for it as two and one can't be one at the same time.

If you're thinking how I came up with the above table. I'm going to explain one of them. Considering 7th case, when A[i] is 1, two is 1 i.e. there already exists A[i] which repeats two times. Finally there is 3 A[i]'s. As, there's 3 of them, then two_ and one_ both should reset to 0.

Considering for one_
It's value is 1 for two cases i.e. 2nd and 5th case. Taking 1 is same as considering minterms in K-map.

one_ = (~A[i] & ~two & one) | (A[i] & ~two & ~one)

If ~two is taken common, then

(~A[i] & one) | (A[i] & ~one) will be same as (A[i]^one)

Then,

one_ = (one ^ A[i]) & ~two

Considering for two_
It's value is 1 for two cases i.e. 3rd and 6th case. Taking 1 is same as considering minterms in K-map.

two_ = (~A[i] & two & ~one) | (A[i] & ~two & one)

Bit manipulation for the calculated two_ will work for the problem. But, As you've mentioned

two_ = (A[i] & one) | (~A[i] & two)

The above expression can be easily be obtained using K-map considering don't cares i.e. X for all cases mentioned above as considering X won't affect our solution.

Considering for two_ and considering X
It's value is 1 for two cases i.e. 3rd and 6th case and X for two cases i.e. 4th and 8th case. Now, considering minterms.

two_ = (~A[i] & two & ~one) | (A[i] & ~two & one) |  (~A[i] & two & one) | (A[i] & two & one)

Now, taking common (A & one) and (~A & two) in the above expression, you'll be left with (two|~two) and (one|~one) which is 1. So, we'll be left with

two_ = (A[i] & one) | (~A[i] & two)

For more insights!

Solution 5

There are three status: 0, 1, 2

So cannot use single bit, have to use high/low bit to present them as: 00, 01, 10

Here's the logic:

high/low 00 01 10

x=0 00 01 10

x=1 01 10 00

high is a function of both high and low.

If low == 1 then high = x, else high = high & ~x

We have

high = low & x | high & ~x

This equals to your: "int two_ = A[i] & one | ~A[i] & two;"

Similarly we have low as the function of both high and low:

If high == 1 then low = ~x, else low = low XOR x

View more solutions

Comments

[Egor Skriptunoff]

one contains bits that appear 3k+1 times in array A, two contains bits that appear 3k+2 times in array A.

[user37940]

So in order to solve the problem what we can do is just add the bits of the numbers one by one and take the result mod 3, if the mod is returned 0 then its 0 if 1 its one and if 2 then what ?