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:
- Calculate the XOR sum of arr1 and arr2 separately. XOR sum is the bitwise XOR of all the elements in the array.
- 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.