{"id":7133,"date":"2020-07-25T11:24:50","date_gmt":"2020-07-25T18:24:50","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7133"},"modified":"2020-07-25T12:05:54","modified_gmt":"2020-07-25T19:05:54","slug":"leetcode-1524-number-of-sub-arrays-with-odd-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1524-number-of-sub-arrays-with-odd-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1524. Number of Sub-arrays With Odd Sum"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1524. Number of Sub-arrays With Odd Sum - \u5237\u9898\u627e\u5de5\u4f5c EP345\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/vGTm8rjlDTQ?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>\n<\/div><\/figure>\n\n\n\n<p>Given an array of integers&nbsp;<code>arr<\/code>. Return&nbsp;<em>the number of sub-arrays<\/em>&nbsp;with&nbsp;<strong>odd<\/strong>&nbsp;sum.<\/p>\n\n\n\n<p>As the answer may grow large, the answer&nbsp;<strong>must be<\/strong>&nbsp;computed modulo&nbsp;<code>10^9 + 7<\/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> arr = [1,3,5]\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]\nAll sub-arrays sum are [1,4,9,3,8,5].\nOdd sums are [1,9,3,5] so the answer is 4.\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> arr = [2,4,6]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]\nAll sub-arrays sum are [2,6,12,4,10,6].\nAll sub-arrays have even sum and the answer is 0.\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> arr = [1,2,3,4,5,6,7]\n<strong>Output:<\/strong> 16\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [100,100,99,99]\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [7]\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr.length &lt;= 10^5<\/code><\/li><li><code>1 &lt;= arr[i] &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-1.png\" alt=\"\" class=\"wp-image-7138\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-2.png\" alt=\"\" class=\"wp-image-7140\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1524-ep345-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>We would like to know how many subarrays <strong>end with arr[i]<\/strong> have odd or even sums.<br><\/p>\n\n\n\n<p>dp[i][0] := # end with arr[i] has even sum<br>dp[i][1] := # end with arr[i] has even sum<\/p>\n\n\n\n<p>if arr[i] is even:<\/p>\n\n\n\n<p>&nbsp;&nbsp;dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]<\/p>\n\n\n\n<p>else:<\/p>\n\n\n\n<p>&nbsp;&nbsp;dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1<\/p>\n\n\n\n<p>ans = sum(dp[i][1])<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n) -&gt; 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 numOfSubarrays(vector<int>& arr) {\n    const int n = arr.size();\n    constexpr int kMod = 1e9 + 7;\n    \/\/ dp[i][0] # of subarrays ends with a[i-1] have even sums.\n    \/\/ dp[i][1] # of subarrays ends with a[i-1] have odd sums.\n    vector<vector<int>> dp(n + 1, vector<int>(2));\n    long ans = 0;\n    for (int i = 1; i <= n; ++i) {\n      if (arr[i - 1] &#038; 1) {\n        dp[i][0] = dp[i - 1][1];\n        dp[i][1] = dp[i - 1][0] + 1;\n      } else {\n        dp[i][0] = dp[i - 1][0] + 1;\n        dp[i][1] = dp[i - 1][1];\n      }\n      ans += dp[i][1];\n    }\n    return ans % kMod;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\n\/\/ Author: Huahua\nclass Solution {\n  public int numOfSubarrays(int[] arr) {\n    long ans = 0, odd = 0, even = 0;\n    for (int x : arr) {\n      even += 1;\n      if (x % 2 == 1) {\n        long t = even; even = odd; odd = t;\n      }\n      ans += odd;\n    }\n    return (int)(ans % (int)(1e9 + 7));\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n# Author: Huahua\nclass Solution:\n  def numOfSubarrays(self, arr: List[int]) -> int:\n    ans, odd, even = 0, 0, 0\n    for x in arr:\n      if x & 1:\n        odd, even = even + 1, odd\n      else:\n        odd, even = odd, even + 1\n      ans += odd\n    return ans % int(1e9 + 7)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of integers&nbsp;arr. Return&nbsp;the number of sub-arrays&nbsp;with&nbsp;odd&nbsp;sum. As the answer may grow large, the answer&nbsp;must be&nbsp;computed modulo&nbsp;10^9 + 7. Example 1: Input: arr&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,409,408,200],"class_list":["post-7133","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-even","tag-odd","tag-prefix-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7133","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=7133"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7133\/revisions"}],"predecessor-version":[{"id":7141,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7133\/revisions\/7141"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7133"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}