Find unique number among 3n+1 numbers [duplicate]

Question

I have been asked this question in an interview.

Given that, there are 3n+1 numbers. n of those numbers occur in triplets, only 1 occurs single time. How do we find the unique number in linear time i.e., O(n) ? The numbers are not sorted.

Note that, if there were 2n+1 numbers, n of which occur in pairs, we could just XOR all the numbers to find the unique one. The interviewer told me that it can be done by bit manipulation.

Answer 1

1. Count the number of times that each bit occurs in the set of 3n+1 numbers.
2. Reduce each bit count modulo 3.
3. What is left is the bit pattern of the single number.

Oh, dreamzor (above) has beaten me to it.

Answer 2

You can invent a 3nary XOR (call it XOR3) operation which operates in base 3 instead of base 2 and simply takes each 3nary digit modulo 3 (when usual XOR takes 2nary digit modulo 2).

Then, if you XOR3 all the numbers (converting them to 3nary first) this way, you will be left with the unique number (in base 3 so you will need to convert it back).

The complexity is not exactly linear, though, because the conversions from/to base 3 require additional logarithmic time. However, if the range of numbers is constant then the conversion time is also constant.

Code on C++ (intentionally verbose):

vector<int> to_base3(int num) {
  vector<int> base3;
  for (; num > 0; num /= 3) {
    base3.push_back(num % 3);
  }
  return base3;
}

int from_base3(const vector<int> &base3) {
  int num = 0;
  for (int i = 0, three = 1; i < base3.size(); ++i, three *= 3) {
    num += base3[i] * three;
  }
  return num;
}

int find_unique(const vector<int> &a) {
  vector<int> unique_base3(20, 0); // up to 3^20
  for (int num : a) {
    vector<int> num_base3 = to_base3(num);
    for (int i = 0; i < num_base3.size(); ++i) {
      unique_base3[i] = (unique_base3[i] + num_base3[i]) % 3;
    }
  }

  int unique_num = from_base3(unique_base3);
  return unique_num;
}

int main() {
  vector<int> rands { 1287318, 172381, 5144, 566546, 7123 };
  vector<int> a;
  for (int r : rands) {
    for (int i = 0; i < 3; ++i) {
      a.push_back(r);
    }
  }
  a.push_back(13371337); // unique number

  random_shuffle(a.begin(), a.end());

  int unique_num = find_unique(a);
  cout << unique_num << endl;
}

Answer 3

byte [] oneCount = new byte [32];

int [] test = {1,2,3,1,5,2,9,9,3,1,2,3,9};

for (int n: test) {
    for (int bit = 0; bit < 32; bit++) {
        if (((n >> bit) & 1) == 1) {
            oneCount[bit]++;
            oneCount[bit] = (byte)(oneCount[bit] % 3);
        }
    }
}

int result = 0;
int x = 1;

for (int bit = 0; bit < 32; bit++) {
    result += oneCount[bit] * x;
    x = x << 1;
}

System.out.print(result);

Looks like while I was coding, others gave the main idea