Leetcode 1835. Find XOR Sum of All Pairs Bitwise AND Solution

Problem Explanation

The problem requires finding the XOR sum of the result list that contains bitwise AND of every pair (i, j) of two given arrays, arr1 and arr2.

Approach & Algorithm

To solve this problem, we will follow these steps:

  1. Calculate the XOR sum of arr1 and arr2 separately. XOR sum is the bitwise XOR of all the elements in the array.
  2. Calculate the result as the bitwise AND of the XOR sums of arr1 and arr2.

Example

Let's walk through an example for a better understanding:

1arr1 = [1, 2, 3]
2arr2 = [6, 5]
3
4Step 1: Calculate XOR sum of arr1 and arr2
5        XOR sum of arr1 = 1 XOR 2 XOR 3 = 0
6        XOR sum of arr2 = 6 XOR 5 = 3
7
8Step 2: Calculate result as bitwise AND of XOR sums
9        result = 0 AND 3 = 0
10
11So, the final answer is 0.

Solution in Python

1from typing import List
2
3class Solution:
4    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
5        # Calculate the XOR sum of arr1 and arr2
6        xors1 = 0
7        xors2 = 0
8        for elem1 in arr1:
9            xors1 ^= elem1
10        for elem2 in arr2:
11            xors2 ^= elem2
12            
13        # The XOR sum of the result list is the bitwise AND of the XOR sums of arr1 and arr2
14        return xors1 & xors2

Solution in Java

1import java.util.*;
2
3class Solution {
4    public int getXORSum(int[] arr1, int[] arr2) {
5        // Calculate the XOR sum of arr1 and arr2
6        int xors1 = 0;
7        int xors2 = 0;
8        for (int elem1 : arr1) {
9            xors1 ^= elem1;
10        }
11        for (int elem2 : arr2) {
12            xors2 ^= elem2;
13        }
14        
15        // The XOR sum of the result list is the bitwise AND of the XOR sums of arr1 and arr2
16        return xors1 & xors2;
17    }
18}

Solution in JavaScript

1class Solution {
2    getXORSum(arr1, arr2) {
3        // Calculate the XOR sum of arr1 and arr2
4        let xors1 = 0;
5        let xors2 = 0;
6        for (const elem1 of arr1) {
7            xors1 ^= elem1;
8        }
9        for (const elem2 of arr2) {
10            xors2 ^= elem2;
11        }
12        
13        // The XOR sum of the result list is the bitwise AND of the XOR sums of arr1 and arr2
14        return xors1 & xors2;
15    }
16}

Solution in C++

1#include <vector>
2#include <numeric>
3#include <functional>
4
5class Solution {
6 public:
7  int getXORSum(std::vector<int>& arr1, std::vector<int>& arr2) {
8    // Calculate the XOR sum of arr1 and arr2
9    int xors1 = std::accumulate(arr1.begin(), arr1.end(), 0, std::bit_xor<>());
10    int xors2 = std::accumulate(arr2.begin(), arr2.end(), 0, std::bit_xor<>());
11    
12    // The XOR sum of the result list is the bitwise AND of the XOR sums of arr1 and arr2
13    return xors1 & xors2;
14  }
15};

Solution in C#

1using System;
2using System.Collections.Generic;
3
4class Solution {
5    public int GetXORSum(int[] arr1, int[] arr2) {
6        // Calculate the XOR sum of arr1 and arr2
7        int xors1 = 0;
8        int xors2 = 0;
9        foreach (int elem1 in arr1) {
10            xors1 ^= elem1;
11        }
12        foreach (int elem2 in arr2) {
13            xors2 ^= elem2;
14        }
15        
16        // The XOR sum of the result list is the bitwise AND of the XOR sums of arr1 and arr2
17        return xors1 & xors2;
18    }
19}

Conclusion

The solutions demonstrate an efficient way to solve the XOR sum of the result list that contains bitwise AND of every pair (i, j) of two given arrays. The algorithm explained is straightforward and easy to understand.

Calculating the XOR sum of the input arrays and then applying bitwise AND operation on them helps us to achieve an optimal solution for this problem.