{"id":7385,"date":"2020-09-19T22:44:52","date_gmt":"2020-09-20T05:44:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7385"},"modified":"2020-09-19T22:45:42","modified_gmt":"2020-09-20T05:45:42","slug":"leetcode-1588-sum-of-all-odd-length-subarrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-1588-sum-of-all-odd-length-subarrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1588. Sum of All Odd Length Subarrays"},"content":{"rendered":"\n

Given an array of positive integers arr<\/code>, calculate the sum of all possible odd-length subarrays.<\/p>\n\n\n\n

A subarray is a contiguous subsequence of the array.<\/p>\n\n\n\n

Return the sum of all odd-length subarrays of <\/em>arr<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> arr = [1,4,2,5,3]\nOutput:<\/strong> 58\nExplanation: <\/strong>The odd-length subarrays of arr and their sums are:\n[1] = 1\n[4] = 4\n[2] = 2\n[5] = 5\n[3] = 3\n[1,4,2] = 7\n[4,2,5] = 11\n[2,5,3] = 10\n[1,4,2,5,3] = 15\nIf we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1,2]\nOutput:<\/strong> 3\nExplanation: <\/strong>There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input: arr = [10,11,12]\nOutput:<\/strong> 66\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= arr.length <= 100<\/code><\/li>
  • 1 <= arr[i] <= 1000<\/code><\/li><\/ul>\n\n\n\n
    Solution 0: Brute Force <\/strong><\/h2>\n\n\n\n
    Enumerate all odd length subarrys: O(n^2), each take O(n) to compute the sum.<\/p>\n\n\n\n
    Total time complexity: O(n^3)
    Space complexity: O(1)<\/p>\n\n\n\n
    Solution 1: Running Prefix Sum<\/strong><\/h2>\n\n\n\n
    Reduce the time complexity to O(n^2)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int sumOddLengthSubarrays(vector& arr) {\n    const int n = arr.size();    \n    int ans = 0;\n    for (int i = 0, s = 0; i < n; ++i, s = 0)\n      for (int j = i; j < n; ++j) {\n        s += arr[j];\n        ans += s * ((j - i + 1) & 1);\n      }    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Math<\/strong><\/h2>\n\n\n\n
    Count how many times arr[i] can be in of an odd length subarray
    we chose the start, which can be 0, 1, 2, ... i, i + 1 choices
    we chose the end, which can be i, i + 1, ... n - 1, n - i choices
    Among those 1\/2 are odd length.
    So there will be upper((i + 1) * (n - i) \/ 2) odd length subarrays contain arr[i]<\/p>\n\n\n\n
    ans = sum(((i + 1) * (n - i) + 1) \/ 2 * arr[i] for in range(n))<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int sumOddLengthSubarrays(vector& arr) {\n    const int n = arr.size();\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      ans += ((i + 1) * (n - i) + 1) \/ 2 * arr[i];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays. A subarray is a contiguous subsequence of the array. Return the sum of…<\/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,200],"class_list":["post-7385","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-prefix-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7385","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=7385"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7385\/revisions"}],"predecessor-version":[{"id":7387,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7385\/revisions\/7387"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7385"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7385"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7385"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}