Geek Answers Handbook

Find a unique number among the numbers 3n + 1

I was asked this question in an interview.

Given that there are 3n + 1 numbers. n of these numbers occur in triplets, only one occurs once. How to find the singular in linear time, i.e. O (n)? Numbers are not sorted.

Note that if there were 2n + 1 numbers, n of which occurred in pairs, we could simply find the XOR of all numbers unique. The interviewer told me that this can be done with bit manipulation.

+6
source share
3 answers
  • Count the number of times each bit occurs in a set of 3n + 1 numbers.
  • Reduce the number of bits modulo 3.
  • Only the singular bit diagram remains.

Oh, the dream (above) beat me.

+8
source

You can think of a 3nary XOR operation (call it XOR3 ), which works in base 3 instead of base 2 and simply accepts each 3nary digit modulo 3 (when a regular XOR accepts a 2nary digit modulo 2).

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

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

C ++ code (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; }
+8
source 
 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);

It looks like while I was coding, others gave the main idea

+3
source

More articles:


All Articles