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]
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.

Time complexity

O(n)

Space complexity

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.

Time complexity

O(n)

Space complexity

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.

Time complexity

O(n)

Space complexity

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’.

Time complexity

O(n)

Space complexity

O(1)

Return to Index