Theory

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 with itself

XOR of a number with itself returns 0.

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

XOR of a number with 0

Returns the same number.

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

XOR is associative and commutative

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

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.

``````Example:

Input: [1, 5, 2, 6, 4]
``````

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

In a non-empty array of integers, every number appears twice except for one, find that single number.

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

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.

``````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:

1. Where the bit is set.
2. 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)`

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.

``````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

1. It will return 1 if we take XOR of two different bits i.e. 1^0 = 0^1 = 1.
2. 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.
3. 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)`