{"id":8379,"date":"2021-04-18T10:47:53","date_gmt":"2021-04-18T17:47:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8379"},"modified":"2021-04-18T10:49:17","modified_gmt":"2021-04-18T17:49:17","slug":"leetcode-1835-find-xor-sum-of-all-pairs-bitwise-and","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-1835-find-xor-sum-of-all-pairs-bitwise-and\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND"},"content":{"rendered":"\n<p>The&nbsp;<strong>XOR sum<\/strong>&nbsp;of a list is the bitwise&nbsp;<code>XOR<\/code>&nbsp;of all its elements. If the list only contains one element, then its&nbsp;<strong>XOR sum<\/strong>&nbsp;will be equal to this element.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, the&nbsp;<strong>XOR sum<\/strong>&nbsp;of&nbsp;<code>[1,2,3,4]<\/code>&nbsp;is equal to&nbsp;<code>1 XOR 2 XOR 3 XOR 4 = 4<\/code>, and the&nbsp;<strong>XOR sum<\/strong>&nbsp;of&nbsp;<code>[3]<\/code>&nbsp;is equal to&nbsp;<code>3<\/code>.<\/li><\/ul>\n\n\n\n<p>You are given two&nbsp;<strong>0-indexed<\/strong>&nbsp;arrays&nbsp;<code>arr1<\/code>&nbsp;and&nbsp;<code>arr2<\/code>&nbsp;that consist only of non-negative integers.<\/p>\n\n\n\n<p>Consider the list containing the result of&nbsp;<code>arr1[i] AND arr2[j]<\/code>&nbsp;(bitwise&nbsp;<code>AND<\/code>) for every&nbsp;<code>(i, j)<\/code>&nbsp;pair where&nbsp;<code>0 &lt;= i &lt; arr1.length<\/code>&nbsp;and&nbsp;<code>0 &lt;= j &lt; arr2.length<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>XOR sum<\/strong>&nbsp;of the aforementioned list<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr1 = [1,2,3], arr2 = [6,5]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> 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].\nThe XOR sum = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr1 = [12], arr2 = [4]\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> The list = [12 AND 4] = [4]. The XOR sum = 4.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr1.length, arr2.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= arr1[i], arr2[j] &lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Bit <\/strong><\/h2>\n\n\n\n<p>(a[0] &amp; b[i]) ^ (a[1] &amp; b[i]) ^ &#8230; ^ (a[n-1] &amp; b[i]) = (a[0] ^ a[1] ^ &#8230;  ^ a[n-1]) &amp; b[i]<\/p>\n\n\n\n<p>We can pre compute that xor sum of array A.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int getXORSum(vector<int>& A, vector<int>& B) {\n    int ans = 0;    \n    int xora = 0;\n    for (int a : A) xora ^= a;    \n    for (int b : B) ans ^= (xora & b);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>The&nbsp;XOR sum&nbsp;of a list is the bitwise&nbsp;XOR&nbsp;of all its elements. If the list only contains one element, then its&nbsp;XOR sum&nbsp;will be equal to this element.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[16,217,63],"class_list":["post-8379","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-hard","tag-xor","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8379","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8379"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8379\/revisions"}],"predecessor-version":[{"id":8383,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8379\/revisions\/8383"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8379"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8379"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8379"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}