The Weekly Challenge 306

Odd Sum and Last Element

Solutions on GitHub

Task 1: 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.

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

Logic

Use a prefix sum array to efficiently compute subarray sums. Iterate over all odd lengths (1, 3, 5, ...) and all starting positions, summing up each subarray in O(1) via prefix differences. Overall O(n^2).

Perl Solution

ch-1.pl

use strict; use warnings; sub odd_sum { my @ints = @_; my $n = scalar @ints; my @prefix = (0); for my $i (0 .. $n - 1) { $prefix[$i+1] = $prefix[$i] + $ints[$i]; } my $total = 0; for (my $l = 1; $l <= $n; $l += 2) { for my $start (0 .. $n - $l) { $total += $prefix[$start + $l] - $prefix[$start]; } } return $total; } use Test::More tests => 4; is(odd_sum(2,5,3,6,4), 77, 'Example 1'); is(odd_sum(1,3), 4, 'Example 2'); is(odd_sum(5), 5, 'Single'); is(odd_sum(1,2,3), 12, 'Length 3');

Python Solution

ch-1.py

def odd_sum(arr: list[int]) -> int: n = len(arr) prefix = [0] * (n + 1) for i in range(n): prefix[i + 1] = prefix[i] + arr[i] total = 0 for length in range(1, n + 1, 2): for start in range(n - length + 1): total += prefix[start + length] - prefix[start] return total

Task 2: Last Element

You are given an array of integers, @ints.

Write a script to play a game: pick the two largest integers x and y. If x == y, remove both. If x != y, remove x and replace y with (y - x). Repeat until at most one element remains. Return the last element, or 0 if none.

Example 1

Input: @ints = (3, 8, 5, 2, 9, 2) Output: 1 Step 1: pick 8 and 9 => (3, 5, 2, 1, 2) Step 2: pick 3 and 5 => (2, 2, 1, 2) Step 3: pick 2 and 2 => (1, 2) Step 4: pick 1 and 2 => (1)

Example 2

Input: @ints = (3, 2, 5) Output: 0 Step 1: pick 3 and 5 => (2, 2) Step 2: pick 2 and 2 => ()

Logic

Repeatedly extract the two largest elements. If equal, both disappear. If different, the difference goes back. A max-heap (or sorting) makes it easy to always pick the two largest. Python uses heapq with negated values for a max-heap.

Perl Solution

ch-2.pl

use strict; use warnings; sub last_element { my @ints = @_; @ints = sort { $b <=> $a } @ints; while (@ints >= 2) { my $x = shift @ints; my $y = shift @ints; if ($x != $y) { push @ints, $x - $y; @ints = sort { $b <=> $a } @ints; } } return @ints ? $ints[0] : 0; } use Test::More tests => 6; is(last_element(3,8,5,2,9,2), 1, 'Example 1'); is(last_element(3,2,5), 0, 'Example 2'); is(last_element(5), 5, 'Single'); is(last_element(5,5), 0, 'Two equal'); is(last_element(10,10,10), 10, 'Three equal'); is(last_element(7,3,7), 3, 'Diff');

Python Solution

ch-2.py

import heapq def last_element(ints: list[int]) -> int: heap = [-x for x in ints] heapq.heapify(heap) while len(heap) >= 2: x = -heapq.heappop(heap) y = -heapq.heappop(heap) if x != y: heapq.heappush(heap, -(x - y)) return -heap[0] if heap else 0