# Solving Leetcode Interviews in Seconds with AI: Sum of All Odd Length Subarrays


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1588" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr. A subarray is a contiguous subsequence of the array.   Example 1:  Input: arr = [1,4,2,5,3] Output: 58 Explanation: The odd-length subarrays of arr and their sums are: [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,2] = 7 [4,2,5] = 11 [2,5,3] = 10 [1,4,2,5,3] = 15 If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58 Example 2:  Input: arr = [1,2] Output: 3 Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3. Example 3:  Input: arr = [10,11,12] Output: 66    Constraints:  1 <= arr.length <= 100 1 <= arr[i] <= 1000    Follow up: Could you solve this problem in O(n) time complexity? 

	# Explanation
	Here's a breakdown of the approach, followed by the Python code:

*   **Contribution of each element:** Instead of generating all subarrays, focus on how many times each element `arr[i]` contributes to the sum of odd-length subarrays.
*   **Formula for contribution:** The number of odd-length subarrays that include `arr[i]` can be calculated directly using its index `i` and the array length `n`. The formula involves considering combinations of elements to the left and right of `arr[i]` to form odd-length subarrays.
*   **Efficient Calculation:** Utilize the formula `((i + 1) * (n - i) + 1) // 2` to determine the number of odd-length subarrays each element belongs to, and multiply this count by the element's value, accumulating the result.

*   **Runtime & Storage Complexity:** O(n) runtime complexity, O(1) storage complexity

	
	# Code
	```python
	def sum_odd_length_subarrays(arr: list[int]) -> int:
    """
    Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.
    """
    n = len(arr)
    total_sum = 0
    for i in range(n):
        total_sum += ((i + 1) * (n - i) + 1) // 2 * arr[i]
    return total_sum
	```