# 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 :)