17. Pattern Bitwise XOR

Grokking Interview Pattern Interview

Word count: 2.7kReading time: 16 min

 2024/05/17 

Introduction

再看这篇文章之前可以看一下这个知乎

XOR is a logical bitwise operator that returns 0 (false) if both bits are the same and returns 1 (true) otherwise. In other words, it only returns 1 if exactly one bit is set to 1 out of the two bits in comparison.

It is surprising to know the approaches that the XOR operator enables us to solve certain problems. For example, let’s take a look at the following problem:

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:

1 2	Input: 1, 5, 2, 6, 4 Answer: 3

A straight forward approach to solve this problem can be:

Find the sum of all integers from 1 to n; let’s call it s1.
Subtract all the numbers in the input array from s1; this will give us the missing number.

Another approach is introduced in 6. Pattern Cyclic Sort\3. Find the Missing Number (easy).

This is what the algorithm will look like:

class Solution:
  def findMissingNumber(self, arr):
    n = len(arr) + 1
    # find sum of all numbers from 1 to n.
    s1 = 0
    for i in range (1, n+1):
      s1 += i

    # subtract all numbers in input from sum.
    for i in arr:
      s1 -= i
    
    # s1, now, is the missing number
    return s1

def main():
  sol = Solution()
  arr = [1, 5, 2, 6, 4] 
  print('Missing number is:' + str(sol.findMissingNumber(arr)))

main()

Time & Space complexity: The time complexity of the above algorithm is O(n) and the space complexity is O(1).

What could go wrong with the above algorithm?

While finding the sum of numbers from 1 to n, we can get integer overflow when n is large.

How can we avoid this? Can XOR help us here?

Remember the important property of XOR that it returns 0 if both the bits in comparison are the same. In other words, 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. Following are the set of steps to find the missing number using XOR:

XOR all the numbers from 1 to n, let’s call it x1.
XOR all the numbers in the input array, let’s call it x2.
The missing number can be found by x1 XOR x2.

Here is what the algorithm will look like:

class Solution:
  def findMissingNumber(self, arr):
    n = len(arr) + 1
    # x1 represents XOR of all values from 1 to n
    x1 = 1
    for i in range(2, n+1):
      x1 = x1 ^ i

    # x2 represents XOR of all values in arr
    x2 = arr[0]
    for i in range(1, n-1):
      x2 = x2 ^ arr[i]
    
    # missing number is the xor of x1 and x2
    return x1 ^ x2

def main():
  sol = Solution()
  arr = [1, 5, 2, 6, 4] 
  print('Missing number is:' + str(sol.findMissingNumber(arr)))

main()

Time & Space complexity: The time complexity of the above algorithm is O(n)O(n) and the space complexity is O(1)O(1). The time and space complexities are the same as that of the previous solution but, in this algorithm, we will not have any integer overflow problem.

Important properties of XOR to remember

Following are some important properties of XOR to remember:

Taking XOR of a number with itself returns 0, e.g.,
- 1 ^ 1 = 0
- 29 ^ 29 = 0
Taking XOR of a number with 0 returns the same number, e.g.,
- 1 ^ 0 = 1
- 31 ^ 0 = 31
XOR is Associative & Commutative, which means:
- (a ^ b) ^ c = a ^ (b ^ c)
- a ^ b = b ^ a

In the following chapters, we will apply the XOR pattern to solve some interesting problems.

Single Number (easy)

Top Interview 150 | 136. Single Number Design Gurus Educative.io

Problem Statement

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

Example 1:

1 2	Input: 1, 4, 2, 1, 3, 2, 3 Output: 4

Example 2:

1 2	Input: 7, 9, 7 Output: 9

Constraints:

1 <= nums.length <= 3 * 10^4
-3 10^4 <= nums[i] <= 3 10^4
Each element in the array appears twice except for one element which appears only once.

Solution

One straight forward solution can be to use a HashMap kind of data structure and iterate through the input:

If number is already present in HashMap, remove it.
If number is not present in HashMap, add it.
In the end, only number left in the HashMap is our required single number.

Time and space complexity Time Complexity of the above solution will be O(n) and space complexity will also be O(n).

Can we do better than this using the XOR Pattern?

Solution with XOR

Recall the following two properties of XOR:

It returns zero if we take XOR of two same numbers.
It returns the same number if we XOR with zero.

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.

Code

Here is what our algorithm will look like:

class Solution:
    def findSingleNumber(self, arr):
        num = 0  # Initialize a variable to store the result
        for i in arr:
            num ^= i  # XOR operation to find the single number
        return num

def main():
    sol = Solution()
    arr = [1, 4, 2, 1, 3, 2, 3]
    print(sol.findSingleNumber(arr))

main()

Time Complexity

Time complexity of this solution is O(n) as we iterate through all numbers of the input once.

Space Complexity

The algorithm runs in constant space O(1).

*Two Single Numbers (medium)

260. Single Number III Design Gurus Educative.io

Problem Statement

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:

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

Example 2:

1 2	Input: [2, 1, 3, 2] Output: [1, 3]

Constraints:

1 <= nums.length <= 3 * 10^4
-3 10^4 <= nums[i] <= 3 10^4
Each element in the array appears twice except for two element which appears only once.

Solution

This problem is quite similar to Single Number, the only difference is that, in this problem, we have two single numbers instead of one. Can we still use XOR to solve this problem?

Let’s assume num1 and num2 are the two single numbers. If we do XOR of all elements of the given array, we will be left with XOR of num1 and num2 as all other numbers will cancel each other because all of them appeared twice. Let’s call this XOR n1xn2. Now that we have XOR of num1 and num2, how can we find these two single numbers?

As we know that num1 and num2 are two different numbers, therefore, they should have at least one bit different between them. If a bit in n1xn2 is ‘1’, this means that num1 and num2 have different bits in that place, as we know that we can get ‘1’ only when we do XOR of two different bits, i.e.,

1	1 XOR 0 = 0 XOR 1 = 1

We can take any bit which is ‘1’ in n1xn2 and 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 num1 will be in one group and num2 will be in the other. We can take XOR of all numbers in each group separately to get num1 and num2, as all other numbers in each group will cancel each other. Here are the steps of our algorithm:

Taking XOR of all numbers in the given array will give us XOR of num1 and num2, calling this XOR as n1xn2.
Find any bit which is set in n1xn2. We can take the rightmost bit which is ‘1’. Let’s call this rightmostSetBit.
Iterate through all numbers of the input array to partition them into two groups based on rightmostSetBit. Take XOR of all numbers in both the groups separately. Both these XORs are our required numbers.

Code

Here is what our algorithm will look like:

class Solution:
  def findSingleNumbers(self, 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]


def main():
  sol = Solution()
  print('Single numbers are:' +
        str(sol.findSingleNumbers([1, 4, 2, 1, 3, 5, 6, 2, 3, 5])))
  print('Single numbers are:' + str(sol.findSingleNumbers([2, 1, 3, 2])))


main()

Time Complexity

The time complexity of this solution is O(n) where ‘n’ is the number of elements in the input array.

Space Complexity

The algorithm runs in constant space O(1).

*Complement of Base 10 Number (medium)

1009. Complement of Base 10 Integer Design Gurus Educative.io

Problem Statement

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:

1
2
3

Input: 8
Output: 7
Explanation: 8 is 1000 in binary, its complement is 0111 in binary, which is 7 in base-10.

Example 2:

1
2
3

Input: 10
Output: 5
Explanation: 10 is 1010 in binary, its complement is 0101 in binary, which is 5 in base-10.

Constraints:

0 <= n < 10^9

Solution

Recall the following properties of XOR:

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:

1	number ^ complement = all_bits_set

Let’s add ‘number’ on both sides:

1	number ^ number ^ complement = number ^ all_bits_set

From the above-mentioned second property:

1	0 ^ complement = number ^ all_bits_set

From the above-mentioned third property:

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

Code

Here is what our algorithm will look like:

class Solution:
  def bitwiseComplement(self, num):
    # count number of total bits in 'num'
    bit_count = 0
    n = num
    while n > 0:
      bit_count += 1
      n = n >> 1

    # 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'
    all_bits_set = pow(2, bit_count) - 1

    # from the solution description: complement = number ^ all_bits_set
    return num ^ all_bits_set

sol = Solution()
print('Bitwise complement is: ' + str(sol.bitwiseComplement(8)))
print('Bitwise complement is: ' + str(sol.bitwiseComplement(10)))

Time Complexity

Time complexity of this solution is O(b) where ‘b’ is the number of bits required to store the given number.

Space Complexity

Space complexity of this solution is O(1)

#Problem Challenge 1

832. Flipping an Image Design Gurus Educative.io

Problem Statement

Given a binary matrix representing an image, we want to flip the image horizontally, then invert it.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [0, 1, 1] horizontally results in [1, 1, 0].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [1, 1, 0] results in [0, 0, 1].

Example 1:

Input: [
  [1,0,1],
  [1,1,1],
  [0,1,1]
]
Output: [
  [0,1,0],
  [0,0,0],
  [0,0,1]
]

Explanation: First reverse each row: [[1,0,1],[1,1,1],[1,1,0]]. Then, invert the image: [[0,1,0],[0,0,0],[0,0,1]]

Example 2:

Input: [
  [1,1,0,0],
  [1,0,0,1],
  [0,1,1,1], 
  [1,0,1,0]
]
Output: [
  [1,1,0,0],
  [0,1,1,0],
  [0,0,0,1],
  [1,0,1,0]
]

Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]. Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Constraints:

n == arr.length
n == arr[i].length
1 <= n <= 20
arr[i][j] is either 0 or 1.

Try it yourself

Try solving this question here:

# 看solution写的
def flip_an_invert_image(matrix):
    for row in matrix:
        C = len(row)
        for i in range((C + 1) // 2):
            row[i], row[C - i - 1] = row[C - i - 1] ^ 1, row[i] ^ 1
    return matrix


def main():
    res = flip_an_invert_image([[1, 0, 1], [1, 1, 1], [1, 1, 0]])
    print(str(res))
    res = flip_an_invert_image([[0, 0, 1, 1], [1, 0, 0, 1], [1, 1, 1, 0], [0, 1, 0, 1]])
    print(str(res))


if __name__ == '__main__':
    main()

Solution

Flip: We can flip the image in place by replacing ith element from left with the ith element from the right.
Invert: We can take XOR of each element with 1. If it is 1 then it will become 0 and if it is 0 then it will become 1.

Code

Here is what our algorithm will look like:

class Solution:
  def flipAndInvertImage(self, matrix):
    C = len(matrix[0])  # Get the number of columns in the matrix
    for row in matrix:
      for i in range((C+1)//2):  # Iterate through the first half of the row
        # Swap and invert elements symmetrically from the beginning and end of the row
        row[i], row[C - i - 1] = row[C - i - 1] ^ 1, row[i] ^ 1
        
    return matrix

def main():
  sol = Solution()
  print(sol.flipAndInvertImage([[1,0,1], [1,1,1], [0,1,1]]))
  print(sol.flipAndInvertImage([[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]))

main()

Time Complexity

The time complexity of this solution is O(n)as we iterate through all elements of the input.

Space Complexity

The space complexity of this solution is O(1).

Author：Hasuer

Link：https://hasuer.github.io/17-pattern-bitwise-xor/index.html

Publish date：May 17th 2024, 4:19:24 pm

Update date：May 28th 2024, 11:29:34 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

Next Post

18. Pattern Top 'K' Elements
Previous Post

16. Pattern Modified Binary Search