**In an array, all numbers appear three times except one which only appears only once. Please find the unique number.**

__Problem:__

**It is simpler if we modify the problem a little bit: Please find a unique number from an array where other numbers appear twice. We could solve this simplified problem with the XOR bitwise operation. If all numbers in the array are XORed, the result is the number appearing only once, since pairs of numbers get 0 when they are XORed.**

__Analysis:__The strategy with XOR does not work since all numbers except one appear three times, since the XOR result of a triple of numbers is the number itself.

Even though we could not solve the problem with XOR, we may still stick on the bitwise operations. A number appears three times, each bit (either 0 or 1) also appears three times. If every bit of numbers appearing three time is added, the sum of every bit should be multiple of 3.

Supposing every bit of numbers (including the unique number) in the input array is added. If the sum of a bit is multiple of 3, the corresponding bit in the unique number is 0. Otherwise, it is 1.

The solution can be implemented in Java as the code listed below:

public static int FindNumberAppearingOnce(int[] numbers) {

for(int i = 0; i < 32; ++i) {

bitSum[i] = 0;

}

for(int i = 0; i < numbers.length; ++i) {

int bitMask = 1;

for(int j = 31; j >= 0; --j) {

int bit = numbers[i] & bitMask;

if(bit != 0) {

bitSum[j] += 1;

}

bitMask = bitMask << 1;

}

}

int result = 0;

for(int i = 0; i < 32; ++i) {

result = result << 1;

result += bitSum[i] % 3;

}

return result;

}

The time efficiency of this solution is O(

*n*), and space efficiency is O(1) because an array with 32 elements is created. It's more efficient than two straightforward solutions: (1) It's easy to find the unique number from a sorted array, but it costs O(

*n*log

*n*) time to sort an array with

*n*elements. (2) We may utilize a hash table to store the number of occurrences of each element in the array, but the cost for the hash table is O(

*n*).

Code with unit tests is shared at http://ideone.com/tTk3RX.

More coding interview questions are discussed in my book<
Coding Interviews: Questions, Analysis & Solutions>. You may find the
details of this book on Amazon.com,
or Apress.

The author Harry He
owns all the rights of this post. If you are going to use part of or the whole
of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/.
If you are going to use it in your books, please contact him via
zhedahht@gmail.com . Thanks.

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteNot clear what is happening if bitSum[I]℅3 gives 2. You mentioned 0 and 1 as possible result of this operation. But I do not see a check of the remaining part equals 2 case.

ReplyDeleteThe bits in binary representation can only be 0 or 1.

DeleteMy shortest solution:

ReplyDeletepublic static int findUnique(int[] a) {

int first = 0, second = 0;

for (int i = 0; i < a.length; i++) {

first = first ^ a[i] ^ (second & a[i]);

second = second ^ a[i] ^ (first & a[i]);

}

return first;

}