# 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.