{"id":8464,"date":"2021-08-04T22:03:21","date_gmt":"2021-08-05T05:03:21","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8464"},"modified":"2021-08-04T22:04:10","modified_gmt":"2021-08-05T05:04:10","slug":"leetcode-1863-sum-of-all-subset-xor-totals","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-1863-sum-of-all-subset-xor-totals\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1863. Sum of All Subset XOR Totals"},"content":{"rendered":"\n<p>The&nbsp;<strong>XOR total<\/strong>&nbsp;of an array is defined as the bitwise&nbsp;<code>XOR<\/code>&nbsp;of<strong>&nbsp;all its elements<\/strong>, or&nbsp;<code>0<\/code>&nbsp;if the array is<strong>&nbsp;empty<\/strong>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, the&nbsp;<strong>XOR total<\/strong>&nbsp;of the array&nbsp;<code>[2,5,6]<\/code>&nbsp;is&nbsp;<code>2 XOR 5 XOR 6 = 1<\/code>.<\/li><\/ul>\n\n\n\n<p>Given an array&nbsp;<code>nums<\/code>, return&nbsp;<em>the&nbsp;<strong>sum<\/strong>&nbsp;of all&nbsp;<strong>XOR totals<\/strong>&nbsp;for every&nbsp;<strong>subset<\/strong>&nbsp;of&nbsp;<\/em><code>nums<\/code>.&nbsp;<\/p>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;Subsets with the&nbsp;<strong>same<\/strong>&nbsp;elements should be counted&nbsp;<strong>multiple<\/strong>&nbsp;times.<\/p>\n\n\n\n<p>An array&nbsp;<code>a<\/code>&nbsp;is a&nbsp;<strong>subset<\/strong>&nbsp;of an array&nbsp;<code>b<\/code>&nbsp;if&nbsp;<code>a<\/code>&nbsp;can be obtained from&nbsp;<code>b<\/code>&nbsp;by deleting some (possibly zero) elements of&nbsp;<code>b<\/code>.<\/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> nums = [1,3]\n<strong>Output:<\/strong> 6\n<strong>Explanation: <\/strong>The 4 subsets of [1,3] are:\n- The empty subset has an XOR total of 0.\n- [1] has an XOR total of 1.\n- [3] has an XOR total of 3.\n- [1,3] has an XOR total of 1 XOR 3 = 2.\n0 + 1 + 3 + 2 = 6\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> nums = [5,1,6]\n<strong>Output:<\/strong> 28\n<strong>Explanation: <\/strong>The 8 subsets of [5,1,6] are:\n- The empty subset has an XOR total of 0.\n- [5] has an XOR total of 5.\n- [1] has an XOR total of 1.\n- [6] has an XOR total of 6.\n- [5,1] has an XOR total of 5 XOR 1 = 4.\n- [5,6] has an XOR total of 5 XOR 6 = 3.\n- [1,6] has an XOR total of 1 XOR 6 = 7.\n- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.\n0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [3,4,5,6,7,8]\n<strong>Output:<\/strong> 480\n<strong>Explanation:<\/strong> The sum of all XOR totals for every subset is 480.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 12<\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 20<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n<p>Use an array A to store all the xor subsets, for a given number x<br>A = A + [x ^ a for a in A]<\/p>\n\n\n\n<p>Time complexity: O(2<sup>n<\/sup>)<br>Space complexity: O(2<sup>n<\/sup>)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def subsetXORSum(self, nums: List[int]) -> int:    \n    xors = [0]\n    for x in nums:\n      xors += [xor ^ x for xor in xors]    \n    return sum(xors)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>The&nbsp;XOR total&nbsp;of an array is defined as the bitwise&nbsp;XOR&nbsp;of&nbsp;all its elements, or&nbsp;0&nbsp;if the array is&nbsp;empty. For example, the&nbsp;XOR total&nbsp;of the array&nbsp;[2,5,6]&nbsp;is&nbsp;2 XOR 5 XOR 6&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,126],"tags":[493,63],"class_list":["post-8464","post","type-post","status-publish","format-standard","hentry","category-array","category-bit","tag-subset","tag-xor","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8464","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=8464"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8464\/revisions"}],"predecessor-version":[{"id":8466,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8464\/revisions\/8466"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}