{"id":3811,"date":"2018-09-01T23:44:25","date_gmt":"2018-09-02T06:44:25","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3811"},"modified":"2018-09-04T12:41:01","modified_gmt":"2018-09-04T19:41:01","slug":"leetcode-898-bitwise-ors-of-subarrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-898-bitwise-ors-of-subarrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 898. Bitwise ORs of Subarrays"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 898. Bitwise ORs of Subarrays - \u5237\u9898\u627e\u5de5\u4f5c EP222\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/E_0BhmAUVNQ?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>We have an array\u00a0<code>A<\/code>\u00a0of non-negative integers.<\/p>\n<p>For every (contiguous) subarray\u00a0<code>B =\u00a0[A[i], A[i+1], ..., A[j]]<\/code>\u00a0(with\u00a0<code>i &lt;= j<\/code>), we take the bitwise OR of all the elements in\u00a0<code>B<\/code>, obtaining a result\u00a0<span style=\"font-family: monospace;\"><code>A[i] | A[i+1] | ... | A[j]<\/code>.<\/span><\/p>\n<p>Return the number of possible\u00a0results.\u00a0 (Results that occur more than once are only counted once in the final answer.)<\/p>\n<div>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[0]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">1<\/span>\r\n<strong>Explanation: <\/strong>\r\nThere is only one possible result: 0.\r\n<\/pre>\n<div>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-2-1\">[1,1,2]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-2\">3<\/span>\r\n<strong>Explanation: <\/strong>\r\nThe possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].\r\nThese yield the results 1, 1, 2, 1, 3, 3.\r\nThere are 3 unique values, so the answer is 3.\r\n<\/pre>\n<div>\n<p><strong>Example 3:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-3-1\">[1,2,4]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-3\">6<\/span>\r\n<strong>Explanation: <\/strong>\r\nThe possible results are 1, 2, 3, 4, 6, and 7.<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= A.length &lt;= 50000<\/code><\/li>\n<li><code>0 &lt;= A[i] &lt;= 10^9<\/code><\/li>\n<\/ol>\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\"><br \/>\n<\/ins><br \/>\n<img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3824\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/898-ep222.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/898-ep222.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/898-ep222-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/898-ep222-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution 1: DP (TLE)<\/strong><\/h1>\n<p>dp[i][j] := A[i] | A[i + 1] | &#8230; | A[j]<\/p>\n<p>dp[i][j] = dp[i][j &#8211; 1] | A[j]<\/p>\n<p>ans = len(set(dp))<\/p>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n^2) -&gt; O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ SC O(n^2)<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: TLE (73\/83 passed).\r\nclass Solution {\r\npublic:\r\n  int subarrayBitwiseORs(vector&lt;int&gt;&amp; A) {\r\n    int n = A.size();\r\n    vector&lt;vector&lt;int&gt;&gt; dp(n, vector&lt;int&gt;(n));\r\n    unordered_set&lt;int&gt; ans(begin(A), end(A));\r\n    for (int l = 1; l &lt;= n; ++l)\r\n      for (int i = 0; i &lt;= n - l; ++i) {        \r\n        int j = i + l - 1;\r\n        if (l == 1) {\r\n          dp[i][j] = A[i];\r\n          continue;\r\n        }\r\n        dp[i][j] = dp[i][j - 1] | A[j];\r\n        ans.insert(dp[i][j]);\r\n      }\r\n    return ans.size();\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ SC O(n)<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: TLE (75\/83 passed)\r\nclass Solution {\r\npublic:\r\n  int subarrayBitwiseORs(vector&lt;int&gt;&amp; A) {\r\n    int n = A.size();\r\n    vector&lt;int&gt; dp(A);\r\n    unordered_set&lt;int&gt; ans(begin(A), end(A));\r\n    for (int l = 2; l &lt;= n; ++l)\r\n      for (int i = 0; i &lt;= n - l; ++i)        \r\n        ans.insert(dp[i] |= A[i + l - 1]);\r\n    return ans.size();\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: DP opted<\/strong><\/h1>\n<p>dp[i] :=\u00a0{A[i], A[i] | A[i &#8211; 1], A[i] | A[i &#8211; 1] | A[i &#8211; 2], &#8230; , A[i] | A[i &#8211; 1] | &#8230; | A[0]}, bitwise ors of all subarrays end with A[i].<\/p>\n<p>|dp[i]| &lt;= 32<\/p>\n<p>Proof: all the elements (in the order of above sequence) in dp[i] are monotonically increasing by flipping 0 bits to 1 from A[i].<\/p>\n<p>There are at most 32 0s in A[i]. Thus the size of the set is &lt;= 32.<\/p>\n<p>\u8bc1\u660e\uff1a dp[i] = {A[i], A[i] | A[i &#8211; 1], A[i] | A[i &#8211; 1] | A[i &#8211; 2], &#8230; , A[i] | A[i &#8211; 1] | &#8230; | A[0]}\uff0c\u8fd9\u4e2a\u5e8f\u5217\u5355\u8c03\u9012\u589e\uff0c\u901a\u8fc7\u628aA[i]\u4e2d\u76840\u53d8\u62101\u3002A[i]\u6700\u591a\u670932\u4e2a0\u3002\u6240\u4ee5\u8fd9\u4e2a\u96c6\u5408\u7684\u5927\u5c0f &lt;= 32\u3002<\/p>\n<p>e.g. \u4e3e\u4f8b\uff1aWorst Case \u6700\u574f\u60c5\u51b5 A = [8, 4, 2, 1, 0] A[i] = 2^(n-i)\u3002<\/p>\n<p>A[5] = 0\uff0cdp[5] = {0, 0 | 1, 0 | 1 | 2, 0 | 1 | 2 | 4, 0 | 1 | 2 | 4 | 8} = {0, 1, 3, 7, 15}.<\/p>\n<p>Time complexity: O(n*log(max(A))) &lt; O(32n)<\/p>\n<p>Space complexity: O(n*log(max(A)) &lt; O(32n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 456 ms\r\nclass Solution {\r\npublic:\r\n  int subarrayBitwiseORs(vector&lt;int&gt;&amp; A) {\r\n    unordered_set&lt;int&gt; ans;\r\n    unordered_set&lt;int&gt; cur;\r\n    unordered_set&lt;int&gt; nxt;\r\n    for (int a : A) {\r\n      nxt.clear();\r\n      nxt.insert({a});\r\n      for (int b : cur) {\r\n        nxt.insert(a | b);\r\n      }\r\n      cur.swap(nxt);\r\n      ans.insert(begin(cur), end(cur));\r\n    }\r\n    return ans.size();\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 434 ms\r\nclass Solution {\r\n  public int subarrayBitwiseORs(int[] A) {\r\n    Set&lt;Integer&gt; ans = new HashSet&lt;&gt;();\r\n    Set&lt;Integer&gt; cur = new HashSet&lt;&gt;();\r\n    for (int a : A) {\r\n      Set&lt;Integer&gt; nxt = new HashSet&lt;&gt;();\r\n      nxt.add(a);\r\n      for (int b : cur)\r\n        nxt.add(a | b);\r\n      ans.addAll(nxt);\r\n      cur = nxt;\r\n    }\r\n    return ans.size();\r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \"># Author: Huahua\r\n# Running time: 812 ms\r\nclass Solution:\r\n  def subarrayBitwiseORs(self, A):\r\n    cur = set()\r\n    ans = set()\r\n    for a in A:\r\n      cur = {a | b for b in cur} | {a}\r\n      ans |= cur      \r\n    return len(ans)<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem We have an array\u00a0A\u00a0of non-negative integers. For every (contiguous) subarray\u00a0B =\u00a0[A[i], A[i+1], &#8230;, A[j]]\u00a0(with\u00a0i &lt;= j), we take the bitwise OR of all the&#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,46],"tags":[16,18,177],"class_list":["post-3811","post","type-post","status-publish","format-standard","hentry","category-bit","category-dynamic-programming","tag-bit","tag-dp","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3811","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=3811"}],"version-history":[{"count":15,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3811\/revisions"}],"predecessor-version":[{"id":3869,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3811\/revisions\/3869"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3811"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3811"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3811"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}