Coding Patterns: Bitwise XOR
In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.
Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge, 0/1 Knapsack and Topological Sort patterns and today, we will introduce Bitwise XOR pattern which is very surprising to know the approaches that the XOR operator (^) enables us to solve certain problems.
If you are not familiar with binary computation and bit manipulation, I strongly recommend to read these two posts first:
Problem: Single Number
LeetCode 136 - Single Number [easy]
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2, 2, 1]
Output: 1
Example 2:
Input: [4, 1, 2, 1, 2]
Output: 4
Bitwise XOR Solution
Recall the following two properties of XOR:
- It returns 0 if we take XOR of two same numbers.
- It returns the same number if we 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.
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
num = 0
for i in nums:
num ^= i
return num
Time Complexity: O(N) where N is the total number of elements in the input array.
Space Complexity: O(1)
Problem: Single Number III
LeetCode 260 - Single Number III [medium]
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
Example:
Input: [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Note:
- The order of the result is not important. So in the above example, [5, 3] is also correct.
- Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
Bitwise XOR Solution
Let’s say 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.
Since we now have XOR of
num1andnum2, 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. 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.
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
# XOR of all numbers in the given list
n1xn2 = 0
for num in nums:
n1xn2 ^= num
# rightmost bit which is 1
rightmost_bit = 1
while rightmost_bit & n1xn2 == 0:
rightmost_bit = rightmost_bit << 1
num1, num2 = 0, 0
for num in nums:
if num & rightmost_bit != 0: # the bit is set
num1 ^= num
else: # the bit is not set
num2 ^= num
return [num1, num2]
Time Complexity: O(N) where N is the total number of elements in the input array.
Space Complexity: O(1)
How to identify?
Knowing XOR properties well opens some surprising doors in your problem solving skills. To be able to identify XOR related problems are mostly coming from previous experiences. But if you need to eliminate the same numbers from an integer array, using Bit Manipulation Tricks is extremely helpful.