Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1835.html

1835. Find XOR Sum of All Pairs Bitwise AND

Level

Hard

Description

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.

• For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4, and the XOR sum of [3] is equal to 3.

You are given two 0-indexed arrays arr1 and arr2 that consist only of non-negative integers.

Consider the list containing the result of arr1[i] AND arr2[j] (bitwise AND) for every (i, j) pair where 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of the aforementioned list.

Example 1:

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].

The XOR sum = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0.

Example 2:

Input: arr1 = [12], arr2 = [4]

Output: 4

Explanation: The list = [12 AND 4] = [4]. The XOR sum = 4.

Constraints:

• 1 <= arr1.length, arr2.length <= 10^5
• 0 <= arr1[i], arr2[j] <= 10^9

Solution

Use the distributive law. For integers a, b and c, there is (a ^ b) & c == (a & c) ^ (b & c) and a & (b ^ c) = (a & b) ^ (a & c).

For 0 <= i < arr1.length, the XOR sum of arr1[i] & arr2[j] where 0 <= j < arr2.length is equal to arr1[i] & (arr2[0] ^ arr2[1] ^ ... ^ arr2[arr2.length - 1]).

Therefore, the XOR sum of the list is calculated as follows.

(arr1[0] ^ arr1[1] ^ ... ^ arr1[arr1.length - 1]) & (arr2[0] ^ arr2[1] ^ ... ^ arr2[arr2.length - 1])

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int getXORSum(int[] arr1, int[] arr2) {
          int xor1 = 0, xor2 = 0;
          for (int num : arr1)
              xor1 ^= num;
          for (int num : arr2)
              xor2 ^= num;
          return xor1 & xor2;
      }
  }
  
  ############
  
  class Solution {
      public int getXORSum(int[] arr1, int[] arr2) {
          int a = 0, b = 0;
          for (int v : arr1) {
              a ^= v;
          }
          for (int v : arr2) {
              b ^= v;
          }
          return a & b;
      }
  }
  

• // OJ: https://leetcode.com/problems/find-xor-sum-of-all-pairs-bitwise-and/
  // Time: O(A + B)
  // Space: O(1)
  class Solution {
  public:
      int getXORSum(vector<int>& A, vector<int>& B) {
          int cnt[31] = {};
          for (int b : B) {
              for (int i = 0; i < 31; ++i) {
                  cnt[i] += (b >> i & 1);
              }
          }
          int ans = 0;
          for (int a : A) {
              int x = 0;
              for (int i = 0; i < 31; ++i) {
                  if ((a >> i & 1) == 0 || cnt[i] % 2 == 0) continue;
                  x |= 1 << i;
              }
              ans ^= x;
          }
          return ans;
      }
  };
  

• class Solution:
      def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
          a = reduce(xor, arr1)
          b = reduce(xor, arr2)
          return a & b
  
  ############
  
  # 1835. Find XOR Sum of All Pairs Bitwise AND
  # https://leetcode.com/problems/find-xor-sum-of-all-pairs-bitwise-and
  
  class Solution:
      def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
          xora = xorb = 0
          
          for num in arr1:
              xora ^= num
          
          for num in arr2:
              xorb ^= num
          
          return xora & xorb
  
  

• func getXORSum(arr1 []int, arr2 []int) int {
  	var a, b int
  	for _, v := range arr1 {
  		a ^= v
  	}
  	for _, v := range arr2 {
  		b ^= v
  	}
  	return a & b
  }
  

• function getXORSum(arr1: number[], arr2: number[]): number {
      const a = arr1.reduce((acc, x) => acc ^ x);
      const b = arr2.reduce((acc, x) => acc ^ x);
      return a & b;
  }
  
  

All Problems

All Solutions