Bitwise XOR (exclusive OR) is a binary operation that takes two binary numbers as input and performs the XOR operation on each pair of corresponding bits. In Python, the bitwise XOR operator is represented by the caret symbol (^). It returns 1 if the corresponding bits are different and 0 if they are the same.
Using the Bitwise XOR pattern can be helpful in solving coding interview questions that involve finding unique elements or pairs in an array. Let's explore some example questions and their solutions using this pattern in Python:
Example 1: Find the unique number in an array
Problem Statement: Given an array of integers where every element appears twice, except for one element which appears only once. Find and return the unique number.
Solution:
def find_unique_number(nums): result = 0 for num in nums: result ^= num return result # Example usage arr = [2, 3, 4, 2, 4] print(find_unique_number(arr)) # Output: 3
Explanation: The XOR operation cancels out the repeating elements since A ^ A = 0
. The remaining element that appears only once will be the result.
Example 2: Find two unique numbers in an array
Problem Statement: Given an array of integers where every element appears twice, except for two elements which appear only once. Find and return the two unique numbers.
Solution:
def find_unique_numbers(nums): xor_result = 0 for num in nums: xor_result ^= num # Find the rightmost set bit in xor_result rightmost_set_bit = 1 while (rightmost_set_bit & xor_result) == 0: rightmost_set_bit <<= 1 num1 = 0 num2 = 0 for num in nums: if num & rightmost_set_bit: num1 ^= num else: num2 ^= num return [num1, num2] # Example usage arr = [2, 3, 4, 2, 4, 5] print(find_unique_numbers(arr)) # Output: [3, 5]
Explanation: The XOR operation cancels out the repeating elements, leaving us with the XOR result of the two unique numbers. We then find the rightmost set bit in the XOR result and use it to divide the array elements into two groups. Each group will contain one of the unique numbers, and we XOR all elements in each group to obtain the respective numbers.
These examples demonstrate how the Bitwise XOR pattern can be used to solve coding interview questions efficiently. It leverages the properties of XOR to find unique elements or pairs in an array.