package miscellaneous.bitmanipulation.lc137_singlenumber2;

/**
 * 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?
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(
                new Solution().singleNumber(new int[]{
                        4, 2, 4, 4
                })
        );
        System.out.println(singleNumber5(new int[]{2,1,2,2,1,2,2,1,3,1,1}));
    }

    //    c b a num
    // 0: 0 0 0  1
    // 1: 0 0 1  1
    // 2: 0 1 0  1
    // 3: 0 1 1  1
    // 4: 1 0 0  1
    // 0: 0 0 0  1
    public static int singleNumber5(int[] nums) {
        int one = 0, two = 0, three = 0;
        for (int num : nums) {
            two = two ^ (one & num);
            one = one ^ num ^ three;
            three = three ^ (num & one & two);
        }
        return one;
    }

    // Each bit in ones and same bit in twos combinely means: number of 1's for all nums
    // Importantly, it's wrapped by 3: 00 -> 01 -> 10 -> 00 ...
    // Eg.nums=[ 4,  2,  4,  4 ]
    // one:     100 110 010 010
    // two:     000 000 100 000
    // 2nd bit: 01 ->    -> 10 -> 00
    // 3rd bit:       01 ->
    public int singleNumber2(int[] nums) {
        int ones = 0, twos = 0;
        for (int i = 0; i < nums.length; i++) {
            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;
        }
        return ones;
    }

    // Explaination of elegant solution above
    // we count each bit 1's by hand, one num one bit.
    public int singleNumber(int[] nums) {
        // Count number of 1's on every bit
        byte[] count = new byte[Integer.SIZE];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < Integer.SIZE; j++) {
                count[j] += ((nums[i] >> j) & 1);
                count[j] %= 3;                      // error: must % here to avoid overflow if we use byte[]
            }
        }

        // Belong to target if number of 1's is NOT divisible by 3
        int single = 0;
        for (int i = 0; i < Integer.SIZE; i++) {
            single |= (count[i] << i);
        }
        return single;
    }

}

@@ -502,32 +502,34 @@
      );%0A        
+//
 System.out.print
@@ -543,17 +543,16 @@
 leNumber
-5
 (new int
@@ -583,24 +583,1120 @@
 %7D));%0A    %7D%0A%0A
+    // Fundamentals of binary addition%0A    //  carry = a & b%0A    //  sum = a %5E b (without carry)%0A    // Each bit of one and two represents:%0A    // 000 -%3E 001 -%3E 010 -%3E 100 -%3E 001 ...%0A    // Most significant bit (b3) is 1 only if all other bits are 1%0A    // If most significant bit is 1, clean all other bits%0A    public int singleNumber(int%5B%5D nums) %7B%0A        int b1 = 0, b2 = 0, b3 = 0;%0A        for (int num : nums) %7B%0A            b2 %5E= b1 & num; // b2 += carry of bit-1 + num%0A            b1 %5E= num;      // b1 += num%0A            b3 = b1 & b2;   // b3 = carry of bit-1 + bit-2%0A            b1 &= ~b3;      // clean if b3 is 1%0A            b2 &= ~b3;      // clean if b3 is 1%0A        %7D%0A        return b1;%0A    %7D%0A%0A    // Sum up 1 on each bit and mod 3, remaining is that single num%0A    public int singleNumber4(int%5B%5D nums) %7B%0A        int cnt = 0;%0A        for (int i = 0; i %3C 32; i++) %7B%0A            int sum = 0;%0A            for (int num : nums) %7B%0A                sum += (num %3E%3E i) & 1;%0A            %7D%0A            cnt %7C= (sum %25 3) %3C%3C i; // must be 0 (3's multiple) or 1%0A        %7D%0A        return cnt;%0A    %7D%0A%0A
     //    c 
@@ -1855,9 +1855,9 @@
 mber
-5
+3
 (int
@@ -2764,16 +2764,16 @@
 ne bit.%0A
-
     publ
@@ -2783,32 +2783,33 @@
 int singleNumber
+1
 (int%5B%5D nums) %7B%0A 

single number II