An General Way to Handle All this sort of questions.


  • 243
    Z

    this kind of question the key idea is design a counter that record state. the problem can be every one occurs K times except one occurs M times. for this question, K =3 ,M = 1(or 2) .
    so to represent 3 state, we need two bit. let say it is a and b, and c is the incoming bit.
    then we can design a table to implement the state move.

    current   incoming  next
    a b            c    a b
    0 0            0    0 0
    0 1            0    0 1
    1 0            0    1 0
    0 0            1    0 1
    0 1            1    1 0
    1 0            1    0 0
    

    like circuit design, we can find out what the next state will be with the incoming bit.( we only need find the ones)
    then we have for a to be 1, we have

        current   incoming  next
        a b            c    a b
        1 0            0    1 0
        0 1            1    1 0
    

    and this is can be represented by

    a=a&~b&~c + ~a&b&c
    

    and b can do the same we , and we find that

    b= ~a&b&~c+~a&~b&c
    

    and this is the final formula of a and b and just one of the result set, because for different state move table definition, we can generate different formulas, and this one is may not the most optimised. as you may see other's answer that have a much simple formula, and that formula also corresponding to specific state move table. (if you like ,you can reverse their formula to a state move table, just using the same way but reversely)

    for this questions we need to find the except one
    as the question don't say if the one appears one time or two time ,
    so for ab both

    01 10 => 1
    00 => 0
    

    we should return a|b;
    this is the key idea , we can design any based counter and find the occurs any times except one .
    here is my code. with comment.

    public class Solution {
        
        public int singleNumber(int[] nums) {
            //we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero.
            //#curent  income  ouput
            //# ab      c/c       ab/ab
            //# 00      1/0       01/00
            //# 01      1/0       10/01
            //# 10      1/0       00/10
            // a=~abc+a~b~c;
            // b=~a~bc+~ab~c;
            int a=0;
            int b=0;
            for(int c:nums){
                int ta=(~a&b&c)|(a&~b&~c);
                b=(~a&~b&c)|(~a&b&~c);
                a=ta;
            }
            //we need find the number that is 01,10 => 1, 00 => 0.
            return a|b;
            
        }
    }
    

    this is a general solution . and it comes from the Circuit Design on course digital logic.


  • 0
    W

    Thank you so much! This was the best help I've had on this series of questions so far =)


  • 0
    S

    I agree that this was the most understandable solution for this problem.


  • 0
    S

    Please explain what is up with these three lines-
    int ta=(~a&b&c)|(a&~b&~c);
    b=(~a&~b&c)|(~a&b&~c);
    a=ta;

    Why do you need to store a in temporary variable?


  • 0
    S

    And, I am sorry I didn't understand why do we need to return a | b. Could you explain that a bit?


  • 3
    W

    You need the temporary variable because you need to calculate both a and b on their old values.

    You return a | b since that will give you the number that isn't a part of a triplet: it either occurs twice (10) or once (01), but you don't know if it's stored in a (for twice) or b (for once). However, you do know that one of them is the number you're looking for, and the other is just 0 - thus you can just OR them together to make sure you return the right number.


  • 0
    S

    Thanks a lot Wilson. Internet is the best learning place because of guys like you. :)


  • 0
    Z

    that's correct! thank for explain.:)


  • 1
    Y

    i dont understand.. what a,b means,why c is the coming bit,but in your code ,c is the number.


  • 1
    Z

    i explain using a example of bit, both a ,b, c is bit. but when we actually do , we receive the number, for int it is 32-bit, but for each bit we will do the same logic, for this operation ,we can do it in parallel which is bit operation & | and ~.


  • 0
    R

    How u r obtaining this table for final solutions:
    current incoming next
    a b c a b
    1 0 0 1 0
    0 1 1 1 0
    Shouldn't we looking at outcomes which has 1 at b(1 time "1") rather than 1 at a(2 times "1").
    And if u r considering that 1 at both the places is fine, then we can consider all cases with outcome 01 or 10(total 4 cases).


  • 117
    F

    Many may wonder what 'a', 'b', 'c' means and how can we manipulate a number like one single bit, as you see in the code, a, b and c are all full 32-bit numbers, not bits. I cannot blame readers to have questions like that because the author did not make it very clear.

    In Single Number, it is easy to think of XOR solution because XOR manipulation has such properties:

    1. Commutative: A^B == B^A, this means XOR applies to unsorted arrays just like sorted. (1^2^1^2==1^1^2^2)
    2. Circular: A^B^...^B == A where the count of B's is a multiple of 2.

    So, if we apply XOR to a preceding zero and then an array of numbers, every number that appears twice will have no effect on the final result. Suppose there is a number H which appears just once, the final XOR result will be 0^H^...H where H appears as many as in input array.

    When it comes to Single Number II (every one occurs K=3 times except one occurs M times, where M is not a multiple of K), we need a substitute of XOR (notated as @) which satisfies:

    1. Commutative: A@B == B@A.
    2. Circular: A@B@...@B == A where the count of B's is a multiple of K.

    We need to MAKE the @ operation. This general solution suggests that we maintain a state for each bit, where the state corresponds to how many '1's have appeared on that bit, so we need a int[32] array.

    bitCount = [];
    for (i = 0; i < 32; i++) {
      bitCount[i] = 0;
    }
    

    The state transits like this:

    for (j = 0; j < nums.length; j++) {
        n = nums[j];
        for (i = 0; i < 32; i++) {
            hasBit = (n & (1 << i)) != 0;
            if (hasBit) {
                bitCount[i] = (bitCount[i] + 1) % K;
            }
        }
    }
    

    I use '!=' instead of '>' in 'hasBit = (n & (1 << i)) != 0;' because 1<<31 is considered negative. After this, bitCount will store the module count of appearance of '1' by K in every bit. We can then find the wanted number by inspecting bitCount.

    exept = 0;
    for (i = 0; i < 32; i++) {
      if (bitCount[i] > 0) {
        exept |= (1 << i);
      }
    }
    return exept;
    

    We use bitCount[i] > 0 as condition because there is no tell how many times that exceptional number appears.

    Now let's talk about ziyihao's solution. His solution looks much magical than mine because given a fixed K, we can encode the state into a few bits. In my bitCount version, we have a int[32] array to store the count of each bit but a 32-bit integer is way more than what we need to store just 3 states. So ideally we can have a bit[32][2] structure to store the counts. We name bit[...][0] as 'a' and bit[...][1] as 'b' and the bits of n as 'c' and we have ziyihao's post.

    The AC Javascript code:

    var singleNumber = function(nums) {
        var k, bitCount, i, j, n, hasBit, exept;
        k = 3;
        bitCount = [];
        for (i = 0; i < 32; i++) {
            bitCount[i] = 0;
        }
        for (j = 0; j < nums.length; j++) {
            n = nums[j];
            for (i = 0; i < 32; i++) {
                hasBit = (n & (1 << i)) !== 0;
                if (hasBit) {
                    bitCount[i] = (bitCount[i] + 1) % k;
                }
            }
        }
        exept = 0;
        for (i = 0; i < 32; i++) {
          if (bitCount[i] > 0) {
            exept |= (1 << i);
          }
        }
        return exept;
    }

  • 10
    C

    absolutely the greatest idea, but horrible teaching...


  • 0
    S

    Excellent explaination! I love this one!


  • 0
    Y

    Thank you for your explanation.


  • 0
    T

    I wonder if the Single Number 3 can be implemented the similar solution or not?


  • 0
    N

    Thank you. This comment clarifies the above post and presents a generalized solution for any K. It also shows why returning a|b makes sense.


  • 0
    I

    Great idea (quite confusing explanation though, thanks felixao for more thorough explanation)! One question: how do you come up with a formula that has those properties? The formula works fine, but I tried to come up with it on my own and I can't do it.


  • 1
    W

    Shouldn't we just return b here?


  • 0
    X

    It's like 32 counters in parallel.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.