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 <= 1001 <= arr[i] <= 1000Follow up:
Could you solve this problem in O(n) time complexity?
program main
use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
implicit none
integer, parameter :: n = 100
real(kind=DP), dimension(n) :: arr
integer :: i, j, k
real(kind=DP) :: sum
! read input
do i = 1, n
read (*, *) arr(i)
end do
! compute sum of all odd-length subarrays
sum = 0.0_DP
do i = 1, n - 1
do j = i + 1, n
if (mod(j - i + 1, 2) /= 0) then
sum = sum + sum_of_subarray(arr, i, j)
end if
end do
end do
! print result
write (unit=error_unit, fmt='(F10.2)') sum
contains
function sum_of_subarray(arr, i, j) result(sum)
implicit none
real(kind=DP), intent(in) :: arr(:)
integer, value :: i, j
integer :: k
real(kind=DP) :: sum
sum = 0.0_DP
do k = i, j
sum = sum + arr(k)
end do
end function sum_of_subarray
end program mainAt line 11 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7b888c972960 in ??? #1 0x7b888c9734d9 in ??? #2 0x7b888cbc717b in ??? #3 0x7b888cbc0684 in ??? #4 0x7b888cbc12aa in ??? #5 0x590fed8be301 in MAIN__ #6 0x590fed8be4e8 in main
module odd_length_subarrays
implicit none
private
public :: sum_odd_length_subarrays
contains
function sum_odd_length_subarrays(arr) result(sum)
integer, intent(in) :: arr(:)
integer :: sum
integer :: i, j, k, n
n = size(arr)
sum = 0
do i = 1, n
do j = i + 1, n
do k = j + 1, n
if (mod(k - j, 2) == 1) then
sum = sum + sum(arr(i:k))
end if
end do
end do
end do
end function sum_odd_length_subarrays
end module odd_length_subarrays
program test_odd_length_subarrays
use odd_length_subarrays
implicit none
integer, parameter :: arr1(3) = [1, 4, 2]
integer, parameter :: arr2(2) = [1, 2]
integer, parameter :: arr3(3) = [10, 11, 12]
integer :: sum
sum = sum_odd_length_subarrays(arr1)
write (*, '(A, I0)') 'Sum of odd-length subarrays of arr1: ', sum
sum = sum_odd_length_subarrays(arr2)
write (*, '(A, I0)') 'Sum of odd-length subarrays of arr2: ', sum
sum = sum_odd_length_subarrays(arr3)
write (*, '(A, I0)') 'Sum of odd-length subarrays of arr3: ', sum
end program test_odd_length_subarrays
temp.f95:16:25:
16 | sum = sum + sum(arr(i:k))
| 1
Error: Unclassifiable statement at (1)
temp.f95:25:9:
25 | use odd_length_subarrays
| 1
Fatal Error: Cannot open module file ‘odd_length_subarrays.mod’ for reading at (1): No such file or directory
compilation terminated.
def sumOddLengthSubarrays(arr):
sum = 0
n = len(arr)
for i in range(n):
oddSubarrays = ((i + 1) * (n - i) + 1) // 2
sum += arr[i] * oddSubarrays
return sum
First, we loop through the input array with index i. For each element arr[i], calculate how many odd-length subarrays it appears in by using the formula ((i + 1) * (n - i) + 1) / 2, where n is the length of the array. This gives us the number of odd-length subarrays that have arr[i] in them.
Then, add the product of arr[i] and the number of odd-length subarrays it appears in to the total sum. Finally, return the total sum.
This algorithm runs in O(n) time complexity, where n is the length of the input array.
int sumOddLengthSubarrays(vector<int>& arr) {
int sum = 0, n = arr.size();
for (int i = 0; i < n; i++) {
int oddSubarrays = ((i + 1) * (n - i) + 1) / 2;
sum += arr[i] * oddSubarrays;
}
return sum;
}
First, we loop through the input array with index i. For each element arr[i], calculate how many odd-length subarrays it appears in by using the formula ((i + 1) * (n - i) + 1) / 2, where n is the length of the array. This gives us the number of odd-length subarrays that have arr[i] in them.
Then, add the product of arr[i] and the number of odd-length subarrays it appears in to the total sum. Finally, return the total sum.
This algorithm runs in O(n) time complexity, where n is the length of the input array.