LeetCode Single Number Extended: Element Appears k Times

Overview

A more general version of LeetCode Single Number problem is discussed (appear k times). One general bit operations implementation could pass the OJ for both.

LeetCode Single Number (k Times) Problem

Given an array of integers, every element appears k times except for one. Find that single one who appears l times.

General Solution and Analysis

This problem is actually motivated by the LeetCode Single Number II Discussion . The thing is the discussion is kind of vague there and I will try to rewrite the whole ideas with details explained by myself based on my own understanding.

The idea is we need k counters to keep record of the mod result of the appearances of each bit. We will need an array of int ‘counter’ of size k. counter[i] denotes those bits appearing i times where i >= 0 and i < k, i = 0 indicates the bit appears k times. Every time we need to recalculate all these counters by examining the next number in the input array based on the facts below:

let counter[j] denote any of the 32 bits, A[i] denote the current number we are examining to count to bits in A[i]:

  • if counter[j] is 1, we need to check whether A[i] has 1 on that bit, if so, then counter[j] should be set to zero, otherwise, counter[j] remains to be 1 at that bit, this part is  (counter[j] & ~A[i]),
  • if counter[j] is 0, we need to check whether the previous one counter[j - 1] has 1 on that bit and A[i] has 1 on that bit, if so, then this carry would be added into counter[j] at that bit and make the new bit 1, otherwise, it remains to be 0, this part is (counter[j-1] & A[i])
The original explanation is: every input number a, generate the new counter by x[j] = (x[j-1] & a) (x[j] & ~a). Except x[0] = (x[k] & a) (x[0] & ~a). In the equation, the first part indicates the the carries from previous one. The second part indicates the bits not carried to next one.

You can chose whichever is easier to understand. And the following is the C++ source code which is accepted by LeetCode OJ for both of the Single Number I and II problem:

int singleNumberInner(int A[], int n, int k, int l) {
    k = max(k, l); // (*)
    int *x = new int[k];
    int xt = 0;
    for (int i = 0; i < k; ++i) x[i] = 0;
    x[0] = -1;
    for (int i = 0; i < n; ++i) {
        xt = x[k - 1];
        for (int j = k - 1; j > 0; --j) x[j] = (x[j - 1] & A[i]) | (x[j] & ~A[i]);
        x[0] = (xt & A[i]) | (x[0] & ~A[i]);
    }
    int ret = x[l];
    delete [] x;
    return ret;
}

Another thing need to point out is the (*) line in above code, what if all the other number appears say 3 times while the single number appears for say 100 times? does the above code still work? I would say without (*) it would fail, otherwise, it still works correctly. I will leave this detail for you to think about it.

Finally, the time complexity is O(kn) while the space complexity is O(k) which are not hard to figure out.

Summary

Essentially, the array x[0…k-1] serves as a Mod K machine, x[i] always stores the number appears i times! So I just actually recap this more general version of LeetCode Single Number problem (appear k times). One general bit operations implementation could pass the OJ for both.

Written on November 22, 2014