Find the Single Number

Problem

• Determine the single number of a list using bits manipulation: InterviewBit

Given an array of integers, every element appears thrice except for one which occurs once.
Find that element which does not appear thrice.
Note: Your algorithm should have a linear runtime complexity.
Could you implement it without using extra memory?
Example:
Input: [1, 2, 4, 3, 3, 2, 2, 3, 1, 1]
Output: 4

• Category: Bit manipulation

Solving Process

To solve this problem according to the constraints (linear time complexity and constant space complexity), we must be familiar with bits manipulation. Let’s review some of the core concepts.

Shift operator

00000101 << 1 = 00001010

We just move the bits to the left which means multiplying this number by 2 (Why 2? Because binary is a base 2. In base 10, shifting to the left means multiplying by 10).

To move them to the right, we use the operator >>.

AND operator

The AND operator applied to an int is done bit by bit.

As an example:

    00100101
AND 10100111
------------
    00100101

OR operator

Same thing for the OR operator:

    00100101
OR  10100111
------------
    10100111

Solution

The solution is not that easy to find. In a nutshell, we have to iterate over each bit of each number and check for each bit position if the sum is not a multiple of 3.

Let’s see a simple example:

Input: 5, 6, 5, 5
Output: 6

Now, using bits representation:

5 -> 101
6 -> 110
5 -> 101
5 -> 101

For each bit position, let’s sum the bits:

5 -> 101
6 -> 110
5 -> 101
5 -> 101
     ---
     413

As we said above, let’s check which sum is not a multiple of 3:

5 -> 101
6 -> 110
5 -> 101
5 -> 101
     ---
     413
     xx-

The sum of the positions 1 and 2 are not a multiple of 3, so we have to set the bit to 1 for each of these positions. It gives us:

110 = 6

In Java, we have to iterate over each bit of the integers. Bear in mind an integer is encoded using 32 bits. We can also use the constant Integer.SIZE.

bitPosition variable references the current position. At the end of each loop, we shift the bits to the left. bitPosition starts at 1, then 2 (10), then 4 (100) etc.

The result variable contains the final result. Each time a sum is not a multiple of 3, we position the bit of bitPosition to 1.

The space complexity is O(1). Concerning the time complexity, we iterate 32 times over each element of the list which still gives us a linear complexity.

I did really want to share this solution as I find it extremely elegant :)

Further reading

• Solving Algo publication

Follow me on Twitter @teivah