[LeetCode] Single Number I & II

Single Number I

Problem Statement (link):

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

Analysis:
This problem is very easy if we are allowed to used extra space - use Dictionary (unordered_map in C++) to save all the element while we scan through the array. It's not obvious to solve it without using extra space.

I learned logical operations in my Digital Signal Processing class way back when I was young... the four common operations are: AND, OR, XOR, XNOR. The XOR truth table is shown below:

XOR Truth Table

Input		Output
A	B
0	0	0
0	1	1
1	0	1
1	1	0

We could use XOR idea to solve this problem, i.e., if we XOR all numbers, the same number pairs will become 0, leaving us only the single number. The reason is that 1) XOR operation is commutative, 2) after XOR, the pairs will become 0's, 0 XOR any number will not change that number.

(As a reminder, XOR: same inputs => 0; different inputs => 1. XNOR: same inputs => 1; different inputs => 0)

Code: 

class Solution {
public:
    int singleNumber(int A[], int n) {
        int op = A[0];
        for (int k = 1; k < n; k++) op ^= A[k];
        return op;
    }
};

Take-aways:
XOR is a simple but powerful technique to solve this kind of duplication problem. We need to think out-of-box sometime to find the optimal solution.

Single Number II

Problem Statement (link):

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?

Analysis:
We couldn't apply XOR directly as we did in Single Number I. We need to dive into bit level to see how XOR works.

If two bits are same, XOR change that bit to 0. What operation we could choose if we want to get 0 after applying that operation on the three same bits? Yes, Modulus.

So, think about each number as a 32-bit sequence with 0s and 1s, for each of the 32 bits, we add all numbers' bits together, then take mod(3), the remainder is bit value of the single number.

The time complexity of this algorithm is O(n), space complexity is O(1). More importantly, we could generalize this type of problem to find the single number in array where all other elements repeating m times.

Code:

class Solution {
public:
    int singleNumber(int A[], int n) {
        if (n==0) return 0;
        int out = 0;
        int count;    // value on a bit if we add all numbers' bit value
        for (int i = 0; i < 32; i++) {      // loop thru bit by bit
            count = 0;
            for (int k = 0; k < n; k++) {   // loop thru all number in A[]
                if((A[k] >> i)&1 !=0) count++;
            }
            out = out | (count%3 << i);     // change out bit by bit
        }
        return out;
    }
};