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 all odd-length subarrays of arr.
 
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

Difficulty: introductory

Starter code:

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        

Solutions:
class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
    
    #    last = len(arr)
    #    total = 0
     #   for start in range(len(arr)):
     #       end = start
     #       while end < last:
     #           total += sum(arr[start:end+1])
     #           end += 2   '''
     #       return total
    
        total = 0
        for i in range(len(arr)):
            totalisubarrays = (len(arr) - i) * (i+1) #this represent total number of subarrays in list that has either i as start or end.
            if totalisubarrays % 2 == 1:
                totalisubarrays += 1
            oddisubarrays = totalisubarrays//2
            total += arr[i]*oddisubarrays
        return total
        


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ans = 0
        n = len(arr)
        for i, j in enumerate(arr):
            ans += ((i + 1) * (n - i) + 1) // 2 * j
        return ans
            


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        
        total = 0
        length = 1
        
        while length <= len(arr):
            for i in range(len(arr)-length+1):
                total += sum(arr[i:i+length])
            length += 2
            
        return total

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        l=len(arr)
        s=0
        for i in range(l):
            for j in range(i+1,l+1,2):
                subarr=arr[i:j]
                s+=sum(subarr)
        return s


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        size  = len(arr)

        for n in range(1, size + 1, 2):
            for i in range(size - (n - 1)):
                total += sum(arr[i:i+n])

        return total

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        li = []
        sumv = 0
        n = len(arr)
        for i in range(1, n + 1, 2):
            li.append(i)
        for i in li:
            for j in range(len(arr)):
                if i + j <= n:
                    sumv += sum(arr[j:j + i])
                else:
                    break
        return sumv


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        l = len(arr)
        sumtotal = 0
        for i in range (1,l+1,2):
            for j in range(1,l+1):
                if (j+i-1 < l+1):
                    sumtotal += sum(arr[j-1:j+i-1])
        return(sumtotal)
                


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        res = 0
        n = len(arr)
        
        for k in range(1, n + 1, 2):
            for i, v in enumerate(arr):
                res += v * min(n - k + 1, k, i + 1, n - i)
        
        return res

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total_sum = 0
        sum_arr = [[0] * (len(arr) + 1) for i in range (len(arr))]
        for i in range (len(arr)):
            for j in range (len(arr) - i):
                start = j
                end = j + i + 1
                sub_sum = 0
                if (end - start) == 1:
                    sum_arr[start][end] = arr[start]
                    sub_sum = arr[start]
                else:
                    sub_sum = arr[start] + sum_arr[start + 1][end]
                    sum_arr[start][end] = sub_sum
                if ((end - start) % 2 == 1):
                    total_sum += sub_sum
        return total_sum


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        if arr == []:
            return 0
        
        sum_ = 0
        
        for i in range(len(arr)):
            for j in range(i + 1, len(arr) + 1):
                val = arr[i : j]
                if len(val) % 2 != 0:
                    sum_ += sum(val)
        
        return sum_

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total_sum = 0
        for i in range (len(arr)):
            for j in range (len(arr) - i):
                start = j
                end = j + i + 1
                sub_arr = arr[start:end]
                if ((end - start) % 2 == 1):
                    total_sum += sum(sub_arr)
        return total_sum


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        result = 0
        for i in range(1, len(arr) + 1, 2):
            for j in range(0, len(arr) + 1 - i):
                print(j, j + i)
                result += sum(arr[j : j+i])
                
        return result

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ret = 0
        for i in range(len(arr)):
            ret += arr[i] * ceil((len(arr) - i ) * (i + 1) /2)
        return ret
    
    # 1: 3
    # 4: 3
    # 2: 5
    # 5: 3
#     # 3: 3
    
#     (5-0)//2 -> 2
#     0//2-> 0
#     (5-1)//2 -> 2
#     1//2 -> 0
#     (5-2)//2 -> 1
#     2//2 -> 1


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        xdict = {}
        print(arr[0:1])
        for i in range(0, len(arr)):
            sumx = 0
            for j in range(0,len(arr)-i):
                sumx = sumx + sum(arr[j:j+i+1])
            xdict[i] = sumx
        
        print(xdict)
        sumx = 0
        for i in xdict:
            if i % 2 == 0:
                sumx = sumx + xdict[i]
            
        return sumx

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        s=0
        for i in range(1,len(arr)+1,2):
            for j in range(len(arr)):
                if len(arr[j:j+i])==i:
                    s=s+sum(arr[j:j+i])
                    # print(arr[j:j+i],sum(arr[j:j+i]))
        return s


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        
        for i in range(len(arr)):
            for j in range(len(arr)):
                a = arr[i:j + 1]
                
                if not len(a) % 2 == 0:
                    total += sum(a)
        return total

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        m=len(arr)
        s=0
        a=[]

        for i in range(m):
            t=0
            while t<=m:
                a=arr[i:t]
                t+=1
                if len(a)%2!=0:
                    s=s+sum(a)
        return(s)


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        arrayLength = len(arr) + 1
        oddLengthSum = 0
        
        if (arrayLength <= 2):
            return sum(arr)
        
        for subArrayLength in range(arrayLength)[1::2]:
            for i in range(arrayLength - subArrayLength):
                for value in arr[i:i + subArrayLength]:
                    oddLengthSum += value
        
        return oddLengthSum


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ans = 0
        i = 0
        j = 1
        while True:
            if i > len(arr)-1:
                break
            if len(arr[i:j]) % 2 != 0:
                ans = ans + sum(arr[i:j])
            j += 1
            if j > len(arr):
                i += 1
                j = i+1
        return ans
            


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
#         subArrayLengths = []
#         for i in range(len(arr)):
#             if (i+1)%2!=0:
#                 subArrayLengths.append(i+1)
#         print(subArrayLengths)
        
#         subSum=0
#         totalSum=0
#         totalSum=0
#         subSum=0
#         flag=True
#         subIndex=0
#         while flag==True:
           
            
        
        
#             if subIndex==len(arr) or subIndex==len(arr)-1:
#                 flag = False
#             else:
#                 subIndex+=2
#         return totalSum
       
        flag = True 
        i=1
        subSum = 0
        totalSum = 0
        while flag:
            subFlag = True
            start = 0
            end = i
            while subFlag:
                for j in arr[start:end]:
                    subSum+=j
                if end == len(arr):
                    totalSum += subSum
                    print((subSum, totalSum))

                    subSum = 0
                    subFlag=False
                else:
                    start +=1
                    end += 1
            if i == len(arr) or i == len(arr)-1:
                flag = False
            else:
                i += 2
        
        return totalSum


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        s = 0
        s+=sum(arr)
    
        for j in range(3, len(arr)+1, 2):
            for i in range(0, len(arr)):
                if(len(arr[i:i+j])%2 != 0 and len(arr[i:i+j]) != 1 and                     i+j<=len(arr)):
                    s+=sum(arr[i:i+j])
        return s

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ret = 0
        subArrs = []
        starting = 0
        ending = len(arr)

        for i in range(len(arr)):
            while (ending >= starting):
                if ((ending - starting) % 2 != 0):
                    subArrs += [arr[starting:ending]]
                    ending -= 2
                else:
                    ending -= 1
            starting += 1
            ending = len(arr)

        for i in subArrs:
            for j in i:
                ret += j 
        
        return ret

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        res, n = 0, len(arr)
        for i, a in enumerate(arr):
            res += ((i + 1) * (n - i) + 1) // 2 * a
        return res


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        return self.backtrack(arr, 0, 0, 0)
    
    def backtrack(self, arr,i,end, s):
        if end == len(arr):
            return s
        elif i > end:
            return self.backtrack(arr, 0, end+1,s)
        else:
            if len(arr[i:end+1]) % 2 != 0:
                s += sum(arr[i:end+1])
                return self.backtrack(arr, i+1, end,s)
            else:
                return self.backtrack(arr, i+1, end,s)

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        res = sum(arr)
        for i in range(0, len(arr)):
            count = 2
            while (i+count) < len(arr):
                for j in range(i,count+i+1):
                    res += arr[j]
                count += 2
        return res


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        size  = len(arr)

        for n in range(1, size + 1, 2):
            for i in range(size - (n - 1)):
                for k in range(i, i + n):
                    # total += sum(arr[i:i+n])
                    total += arr[k]

        return total

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        for length in range(1, len(arr)+1):
            if length%2 == 0:
                continue
            for i_start, start in enumerate(arr):
                if i_start + length -1 < len(arr):
                    for i in range(i_start, i_start+length):
                        total += arr[i]
                else:
                    break
        return total

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        
        ans = 0
        for i in range(1, len(arr) + 1, 2):
            for j in range(len(arr) + 1 - i):
                for k in range(i):
                    ans += arr[j + k]
        return ans


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        result = 0
        l = r = 0

        def getSum(array, start, end):
            local_sum = 0
            for i in range(start, end):
                local_sum += array[i]
            return local_sum

        while l < len(arr) - 1:
            if r > len(arr) - 1:
                l += 1
                r = l
            result += getSum(arr, l, r+1)
            r += 2

        return result


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return (arr[0])
        result = 0
        l = r = 0
        def getSum(array, start, end):
            local_sum = 0
            for i in range(start,end):#
                local_sum += array[i]#1,
            return local_sum

        while l < len(arr) - 1:#0<4
            if r > len(arr) - 1:#1>4
                l += 1
                r = l
            result += getSum(arr, l, r+1)#arr,0,2
            r += 2
        return result



class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        cur_sum, prefix_sum = 0, [0] * (len(arr) + 1)
        ret = 0
        for i in range(1, len(arr)+1):
            cur_sum += arr[i-1]
            prefix_sum[i] = cur_sum
            for j in range(1, i+1, 2):
                # print([i, j])
                ret += prefix_sum[i] - prefix_sum[i-j]
        return ret

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        s = 0
        for i in range(n):
            for j in range(1, n+1, 2):
                if i + j - 1 < n:
                    for x in range(j):
                        s += arr[x+i]
        return s

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ans=0
        N=len(arr)
        sumv=(N+1)*[0]
        for i in range(N):
            sumv[i+1]=sumv[i]+arr[i]
        ans=0
        for i in range(1,N+1):
            ans+=(sumv[i]*((i+1)//2-(N-i+1)//2))
        return ans

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        subArrLen = 1
        while subArrLen <= len(arr):
            i = 0
            j = subArrLen
            subTotal = sum(arr[:j])
            total += subTotal
            while j < len(arr):
                subTotal -= arr[i]
                subTotal += arr[j]
                total += subTotal
                i += 1
                j += 1
            subArrLen += 2
            
        return total


class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n, sum_odd = len(arr), 0
        p_sum = [0] * ( n + 1)
        for i, a in enumerate(arr):
            p_sum[i + 1] = p_sum[i] + a
        for i, p in enumerate(p_sum):
            for j in range(i + 1, n + 1, 2):
                sum_odd += p_sum[j] - p_sum[i] 
        return sum_odd

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        prefix = [0]*(n+1)
        for i in range(n): prefix[i] = prefix[i-1]+arr[i]
        ans = 0
        for s in range(1,n+1,2): 
            for i in range(n):
                if i+s > n: break
                ans += prefix[i+s-1] - prefix[i-1]
        return ans 

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total=0
        for i in range(len(arr)):
            temp=0
            for j in range (i,len(arr)):               
                temp+=arr[j] 
                if(j-i)%2 ==0:
                    total+=temp
        return total