{"id":1243,"date":"2017-12-14T18:36:14","date_gmt":"2017-12-15T02:36:14","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1243"},"modified":"2017-12-14T21:10:42","modified_gmt":"2017-12-15T05:10:42","slug":"leetcode-477-total-hamming-distance","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-477-total-hamming-distance\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 477. Total Hamming Distance"},"content":{"rendered":"<div class=\"question-description\">\n<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 477. Total Hamming Distance - \u5237\u9898\u627e\u5de5\u4f5c EP132\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/fH9clXXrS2Q?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>The\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Hamming_distance\" target=\"_blank\" rel=\"noopener\">Hamming distance<\/a>\u00a0between two integers is the number of positions at which the corresponding bits are different.<\/p>\n<p>Now your job is to find the total Hamming distance between all pairs of the given numbers.<\/p>\n<p><b>Example:<\/b><\/p>\n<pre class=\"\">Input: 4, 14, 2\r\n\r\nOutput: 6\r\n\r\nExplanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just\r\nshowing the four bits relevant in this case). So the answer will be:\r\nHammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>Elements of the given array are in the range of\u00a0<code>0\u00a0<\/code>to\u00a0<code>10^9<\/code><\/li>\n<li>Length of the array will not exceed\u00a0<code>10^4<\/code>.<\/li>\n<\/ol>\n<p><strong>\u9898\u76ee\u5927\u610f\uff1a<\/strong>\u7ed9\u4f60\u4e00\u5806\u6570\uff0c\u8ba9\u4f60\u6c42\u6240\u6709\u6570\u5bf9\u7684HammingDistance\u7684\u603b\u548c\u3002<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<ol>\n<li>Brute force, compute\u00a0HammingDistance for all pairs. O(n^2) TLE<\/li>\n<li>Count how many ones on i-th bit, assuming k. Distance += k * (n &#8211; k). O(n)<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1248\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/477-ep132.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/477-ep132.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/477-ep132-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/477-ep132-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<\/div>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++ \/ O(n)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 59 ms\r\nclass Solution {\r\npublic:\r\n    int totalHammingDistance(vector&lt;int&gt;&amp; nums) {\r\n        int ans = 0;\r\n        int mask = 1;\r\n        for (int i = 0; i &lt; 32; ++i) {\r\n            int count = 0;\r\n            for (const int num : nums)\r\n                if (num &amp; mask) ++count;\r\n            ans += (nums.size() - count) * count;\r\n            mask &lt;&lt;= 1;\r\n        }\r\n        return ans;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: The\u00a0Hamming distance\u00a0between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total&#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,130,189,187],"class_list":["post-1243","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-distance","tag-hamming","tag-mask","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1243","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=1243"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1243\/revisions"}],"predecessor-version":[{"id":1250,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1243\/revisions\/1250"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1243"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}