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 to1 XOR 2 XOR 3 XOR 4 = 4
, and the XOR sum of[3]
is equal to3
.
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 <= 105
0 <= arr1[i], arr2[j] <= 109
Solution: Bit
(a[0] & b[i]) ^ (a[1] & b[i]) ^ … ^ (a[n-1] & b[i]) = (a[0] ^ a[1] ^ … ^ a[n-1]) & b[i]
We can pre compute that xor sum of array A.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 |
class Solution { public: int getXORSum(vector<int>& A, vector<int>& B) { int ans = 0; int xora = 0; for (int a : A) xora ^= a; for (int b : B) ans ^= (xora & b); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment