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

1. It returns 0 if we take XOR of two same numbers.
2. 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 `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. 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.

Tags:

Categories:

Updated: