No. 50 - Numbers Appearing Once

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

Analysis: 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.

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) {

    int[] bitSum = new int[32];
    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(nlogn) 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.