Skills for tackling LeetCode problems - Bitwise XOR.
XOR is a logical bitwise operator that returns 0 (false) if both bits are the same and returns 1 (true) otherwise.
Problem Statement: Given an array of $n-1$ Integers in the range from $1$ to $n$, find the one number that is missing from the array.
The approach to solve this problem is to find the sum of all integers from 1 to n first and subtract all the numbers in the input array from it. This will give us the missing number.
# Time complexity O(N). Space complexity O(1).
def find_missing_number(arr):
n = len(arr) + 1 # the length of the array if there is no missing
SUM = int(n * (n + 1) / 2) # calculate the sum of 1 to n
for i in arr:
SUM -= i # subtract all numbers in the array
return SUM
The problem is we can get integer overflow when n is large. XOR can help us to avoid this. Here are some properties of XOR:
- Taking XOR of a number with itself returns 0.
21 ^ 21 = 0. - Taking XOR of a number with 0 returns the same number.
21 ^ 0 = 21. - XOR is associative and commutative which means:
(a ^ b) ^ c = a ^ (b ^ c)anda ^ b = b ^ a.
XOR returns 0 if both the bits in comparison are the same. In other word, XOR of a number with itself will always result in 0. This means that if we XOR all the numbers in the input array with all numbers from the range 1 to n then each number in the input is going to get zeroed out except the missing number.
# Time complexity O(N). Space complexity O(1).
def find_missing_number(arr):
n = len(arr)
# x1: XOR of all values from 1 to n
x1 = 1
for i in range(2, n + 2):
x1 = x1 ^ i
# x2: XOR of all values in array
x2 = arr[0]
for i in range(1, n):
x2 = x2 ^ arr[i]
# missing number is the XOR of x1 and x2
return x1 ^ x2
1. Single Number
In a non-empty array of integers, every number appears twice except for one, find that single number.
Since XOR of two same numbers returns 0, and it returns the same number if it XOR with 0. So we can XOR all the numbers in the input duplicate numbers will zero out each other and we will be left with the single number.
# Time complexity O(N). Space complexity O(1).
def find_single_number(arr):
num = 0
for i in arr:
num ^= i
return num
2. Two Single Numbers
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.
Since we can get ‘1’ only when we do XOR of two different bits, after doing XOR of all elements of the given array, we will have XOR of the two different numbers, as all others will cancel each other. Since two numbers are different, they should have at least one bit different between them. (e.g. if a bit in the XOR of two different numbers is 1, this means the two numbers have different bits in that place.)
We can partition all numbers in the given array into two groups based on that bit, one group will have all those numbers with that bit set to 0 and the other with the bit set to 1, this will ensure that the two different numbers are in different groups, then we can continue take XOR of all numbers in each group separately until we find those two numbers.
Note the 2 Bitwise operation rules:
n & 1 = 0, the right most bit is 0.n & 1 = 1, the right most bit is 1.
# Time complexity O(N). Space complexity O(1).
def find_single_numbers(nums):
# get the XOR of the all the numbers
n1xn2 = 0
for num in nums:
n1xn2 ^= num
# get the rightmost bit that is '1'
rightmost_set_bit = 1
while (rightmost_set_bit & n1xn2) == 0:
rightmost_set_bit = rightmost_set_bit << 1
num1, num2 = 0, 0
for num in nums:
if (num & rightmost_set_bit) != 0: # the bit is set
num1 ^= num
else: # the bit is not set
num2 ^= num
return [num1, num2]
3. Complement of Base 10 Number
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 a given positive number N is base 10, return the complement of its binary representation as a base 10 integer.
Recall the properties if XOR:
- XOR of two different bits is 1:
1^0 = 0^1 = 1. - XOR of two same bits is 0:
0^0 = 1^1 = 0.
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. 101 ^ 010 = 111. Then, we can write the following equations:
number ^ complement = all_bits_set
number ^ number ^ complement = number ^ all_bits_set
0 ^ complement = number ^ all_bits_set
complement = number ^ all_bits_set
Therefore, we can use complement = number ^ all_bits_set to find the complement of any number.
To acquire the all_bits_set, we will first count the n bits required to store the given number, then apply all_bits_set = pow(2,n) - 1.
# Time complexity O(M) where M is the number of bits required to store the given number. Space complexity O(1).
def calculate_bitwise_complement(num):
bit_count, n = 0, num
while n > 0: # count the bits required to store the given number
bit_count += 1
n = n >> 1 # back
all_bits_set = pow(2, bit_count) - 1
return num ^ all_bits_set
