- Theory
- Questions
- Given an array of n−1 integers in the range from 1 to n, find the one number that is missing from the array.
- In a non-empty array of integers, every number appears twice except for one, find that single number.
- In a non-empty array of numbers, every number appears exactly twice except two numbers that appear only once. Find the two numbers that appear only once.
- Every non-negative integer N has a binary representation, for example, 8 can be represented as “1000” in binary and 7 as “0111” in binary. The complement of a binary representation is the number in binary that we get when we change every 1 to a 0 and every 0 to a 1. For example, the binary complement of “1010” is “0101”. For a given positive number N in base-10, return the complement of its binary representation as a base-10 integer.

XOR (Exclusive-OR) is a special case of OR. OR could be logically ambiguous in certain scenarios where XOR specifically represents *either-or* v/s OR which represents both *either-or* and *both*.

Thus, with XOR, the bit is only set when one of the bits is 1, but not both. Thus,

A | B | A XOR B |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

XOR of a number with itself returns 0.

```
1 ^ 1 = 0
29 ^ 29 = 0
```

Returns the same number.

```
1 ^ 0 = 1
31 ^ 0 = 31
```

```
(a ^ b) ^ c = a ^ (b ^ c)
a ^ b = b ^ a
```

```
Example:
Input: [1, 5, 2, 6, 4]
Answer: 3
```

**Implementation: FindMissingNumber**

When we `XOR`

all numbers till `n`

, it will have a certain set of set bits.

```
1 XOR 10 = 11
11 XOR 11 = 0
0 XOR 100 = 100
100 XOR 101 = 1
1 XOR 110 = 111
```

When we `XOR`

all numbers of the array with a missing number, it will have a different set of set bits because the bits contributed by the missing number wont be there.

```
1 XOR 1 = 100
100 XOR 10 = 110
110 XOR 11 = 0
0 XOR 100 = 100
```

Doing a XOR between these two will give that missing set of bits (`111 ^ 100 = 11`

) and hence the number. Very similar to if we summed both the arrays and found the difference.

`O(n)`

`O(1)`

```
Example 1:
Input: 1, 4, 2, 1, 3, 2, 3
Output: 4
Example 2:
Input: 7, 9, 7
Output: 9
```

**Implementation: SingleNumber**

Since, every number appears twice except one number, if we XOR all numbers, the numbers appearing twice will give a XOR of 0 and only the number that doesn't have a duplicate, will be left.

`O(n)`

`O(1)`

```
Example 1:
Input: [1, 4, 2, 1, 3, 5, 6, 2, 3, 5]
Output: [4, 6]
Example 2:
Input: [2, 1, 3, 2]
Output: [1, 3]
```

**Implementation: TwoSingleNumbers**

Say the two numbers we are trying to find are `n1`

and `n2`

.

If we take the XOR of all elements in the array, we will be left with the XOR of the two numbers (say `n3`

) as all other numbers with their duplicates would cancel each other out.

Now `n3`

will basically only have the bits set where either that bit is set in `n1`

or its set in `n2`

but not both.

So lets pick any set bit.

Now we can differentiate the elements of the array into two different groups:

- Where the bit is set.
- Where the bit is not set.

If we XOR these two groups amongst themselves, all duplicates would cancel out and give the two numbers.

`O(n)`

`O(1)`

```
Example 1:
Input: 8
Output: 7
Explanation: 8 is 1000 in binary, its complement is 0111 in binary, which is 7 in base-10.
Example 2:
Input: 10
Output: 5
Explanation: 10 is 1010 in binary, its complement is 0101 in binary, which is 5 in base-10.
```

**Implementation: ComplementOfBase10**

- It will return 1 if we take XOR of two different bits i.e. 1^0 = 0^1 = 1.
- It will return 0 if we take XOR of two same bits i.e. 0^0 = 1^1 = 0. In other words, XOR of two same numbers is 0.
- It returns the same number if we XOR with 0.

From the above-mentioned first property, we can conclude that XOR of a number with its complement will result in a number that has all of its bits set to 1. For example, the binary complement of “101” is “010”; and if we take XOR of these two numbers, we will get a number with all bits set to 1, i.e., 101 ^ 010 = 111

```
We can write this fact in the following equation:
number ^ complement = all_bits_set
Let’s add ‘number’ on both sides:
number ^ number ^ complement = number ^ all_bits_set
From the above-mentioned second property:
0 ^ complement = number ^ all_bits_set
From the above-mentioned third property:
complement = number ^ all_bits_set
```

We can use the above fact to find the complement of any number.

**How do we calculate ‘all_bits_set’?**

One way to calculate all_bits_set will be to first count the bits required to store the given number. We can then use the fact that for a number which is a complete power of ‘2’ i.e., it can be written as pow(2, n), if we subtract ‘1’ from such a number, we get a number which has ‘n’ least significant bits set to ‘1’. For example, ‘4’ which is a complete power of ‘2’, and ‘3’ (which is one less than 4) has a binary representation of ‘11’ i.e., it has ‘2’ least significant bits set to ‘1’.

`O(n)`

`O(1)`