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.

Don't you love when you are presented with multiple solutions to the same problem. Plent to learn each week. Keep it up great work.

Try it 

#!/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];
}

9 lines of code

Output from script

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