{"id":3640,"date":"2018-08-20T17:31:45","date_gmt":"2018-08-21T00:31:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3640"},"modified":"2018-08-22T22:52:42","modified_gmt":"2018-08-23T05:52:42","slug":"leetcode-891-sum-of-subsequence-widths","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-891-sum-of-subsequence-widths\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 891. Sum of Subsequence Widths"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 891. Sum of Subsequence Widths - \u5237\u9898\u627e\u5de5\u4f5c EP218\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/lfF7XqwXokw?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<h1><strong>Problem<\/strong><\/h1>\n<p>Given an array of integers\u00a0<code>A<\/code>, consider all non-empty subsequences of\u00a0<code>A<\/code>.<\/p>\n<p>For any sequence S, let the\u00a0<em>width<\/em>\u00a0of S be the difference between the maximum and minimum element of S.<\/p>\n<p>Return the sum of the widths of all subsequences of A.<\/p>\n<p>As the answer may be very large,\u00a0<strong>return the answer modulo 10^9 + 7<\/strong>.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[2,1,3]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">6<\/span>\r\n<strong>Explanation:\r\n<\/strong>Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].\r\nThe corresponding widths are 0, 0, 0, 1, 1, 2, 2.\r\nThe sum of these widths is 6.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>1 &lt;= A.length &lt;= 20000<\/code><\/li>\n<li><code>1 &lt;= A[i] &lt;= 20000<\/code><\/li>\n<\/ul>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3669\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/891-ep218.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/891-ep218.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/891-ep218-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/891-ep218-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution: Math<\/strong><\/h1>\n<p>Sort the array, for A[i]:<\/p>\n<ul>\n<li>i numbers &lt;= A[i]. A[i] is the upper bound of 2^i subsequences.<\/li>\n<li>n &#8211; i &#8211; 1 numbers &gt;= A[i]. A[i] is the lower bound of 2^(n &#8211; i &#8211; 1) subsequences.<\/li>\n<li>A[i] contributes\u00a0A[i] * 2^i &#8211;\u00a0A[i] * 2^(n &#8211; i &#8211; 1) to the ans.<\/li>\n<\/ul>\n\\(ans = \\sum\\limits_{i=0}^{n-1}A_{i}2^{i} &#8211; A_{i}2^{n &#8211; i &#8211; 1} =\\sum\\limits_{i=0}^{n-1}(A_i &#8211; A_{n-i-1})2^{i}\\)\n<p>Time complexity: O(nlogn)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 56 ms\r\nclass Solution {\r\npublic:\r\n  int sumSubseqWidths(vector&lt;int&gt;&amp; A) {\r\n    constexpr long kMod = 1e9 + 7;\r\n    const int n = A.size();\r\n    sort(begin(A), end(A));\r\n    long ans = 0;\r\n    long p = 1;\r\n    for (int i = 0; i &lt; n; ++i) {\r\n      ans = (ans + (A[i] - A[n - i - 1]) * p) % kMod;\r\n      p = (p &lt;&lt; 1) % kMod;\r\n    }\r\n    return (ans + kMod) % kMod;\r\n  }\r\n};<\/pre>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<p>Counting sort<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 16 \/ 44 ms (beats 100%)\r\nstatic auto x = [](){std::ios::sync_with_stdio(false);cin.tie(nullptr);return nullptr;}();\r\n\r\nclass Solution {\r\npublic:\r\n  int sumSubseqWidths(vector&lt;int&gt;&amp; A) {\r\n    constexpr long kMod = 1e9 + 7;\r\n    const int n = A.size();    \r\n    countingSort(A);\r\n    long ans = 0;\r\n    long p = 1;\r\n    for (int i = 0; i &lt; n; ++i) {\r\n      ans = (ans + (A[i] - A[n - i - 1]) * p) % kMod;\r\n      p = (p &lt;&lt; 1) % kMod;\r\n    }\r\n    return (ans + kMod) % kMod;\r\n  }\r\nprivate:\r\n  void countingSort(vector&lt;int&gt;&amp; A) {    \r\n    int max_v = INT_MIN;\r\n    int min_v = INT_MAX;\r\n    for (int a : A) {      \r\n      if (a &gt; max_v) max_v = a;\r\n      if (a &lt; min_v) min_v = a;      \r\n    }      \r\n    vector&lt;int&gt; c(max_v - min_v + 1);\r\n    for (int a : A)\r\n      ++c[a - min_v];\r\n    int i = 0;\r\n    int j = 0;\r\n    while (i &lt; c.size()) {\r\n      if (--c[i] &gt;= 0) \r\n        A[j++] = i + min_v;\r\n      else\r\n        ++i;\r\n    }\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given an array of integers\u00a0A, consider all non-empty subsequences of\u00a0A. For any sequence S, let the\u00a0width\u00a0of S be the difference between the maximum and&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,23,229],"class_list":["post-3640","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-sort","tag-subsequence","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3640","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=3640"}],"version-history":[{"count":22,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3640\/revisions"}],"predecessor-version":[{"id":3673,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3640\/revisions\/3673"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3640"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3640"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3640"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}