Task — Odd sum

You are given an array of positive integers, @ints. Write a script to return the sum of all possible odd-length subarrays of the given array. A subarray is a contiguous subsequence of the array.

Examples

Example 1
Input: @ints = (2, 5, 3, 6, 4)
Output: 77
Odd length sub-arrays:
(2) => 2
(5) => 5
(3) => 3
(6) => 6
(4) => 4
(2, 5, 3) => 10
(5, 3, 6) => 14
(3, 6, 4) => 13
(2, 5, 3, 6, 4) => 20
Sum => 2 + 5 + 3 + 6 + 4 + 10 + 14 + 13 + 20 => 77

Example 2
Input: @ints = (1, 3)
Output: 4

Analysis

Once again, I can see two ways to do this.

Method one, which is what I have submitted, loops over the starting and ending elements of all odd-length subarrays, and adds the sum of each such subarray to an overall sum.

This works - a big plus! - but there is another way which might be faster for an enormous array of @ints.

Method 2 involves creating an array @mults, such that the sum of $mults[$i] * $ints[$i] gives the required answer. The value of $mults[$i] is the number of subarrays that include $ints[$i], and clearly is only a function of the length of @ints and not the actual values. However I think the time to calculate @mults is possibly of order $n ** 2 where $n is the length of @ints.

I'll leave it to someone else to do it that way - and to show whether it is faster.

Try it 

Try running the script with any input:

Your @ints =

example: 2, 4, 6, 8, 10

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-01-27
use utf8;     # Week 306 - task 1 - Odd sum
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

odd_sum(2, 5, 3, 6, 4);
odd_sum(99);
odd_sum(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20);

sub odd_sum {
    
    my (@ints, $sum, $start, $end);
    
    # initialise
    @ints = @_;
    $sum = 0;
    
    # loop over start and end points
    for $start (0 .. $#ints) {
        for ($end = $start; $end <= $#ints; $end += 2) {
            $sum += $ints[$_] for $start .. $end;
        }
    }
    
    # report
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . qq[)];
    say qq[Output: $sum];
}

Output

Input:  @ints = (2, 5, 3, 6, 4)
Output: 77

Input:  @ints = (99)
Output: 99

Input:  @ints = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 
13, 14, 15, 16, 17, 18, 19, 20)
Output: 8085