HardNo. 1835

Find XOR Sum of All Pairs Bitwise AND — LeetCode 1835 Python Solution

Topics
Bit Manipulation, Array, Math
Reading time
2 min

The problem

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element.

Example

Input
arr1 = [1,2,3], arr2 = [6,5]
Output
0
Explanation
The list = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1].

Python solution

PythonSolution
class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        a = reduce(xor, arr1)
        b = reduce(xor, arr2)
        return a & b

Complexity

Time
O(n + m)where n and m are the lengths of arrays arr1 and arr2, respectively
Space · auxiliary
O(1)

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0477Total Hamming DistanceMedium
0782Transform to ChessboardHard
0810Chalkboard XOR GameHard
2317Maximum XOR After OperationsMedium
2527Find Xor-Beauty of ArrayMedium
0029Divide Two IntegersMedium

Frequently asked questions

How hard is LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND?

LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND is rated Hard on LeetCode.

What is the time complexity of LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND?

The Python solution on this page runs in O(n + m), where n and m are the lengths of arrays arr1 and arr2, respectively.

What is the space complexity of LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND cover?

LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND is tagged Bit Manipulation, Array and Math on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.