08 November 2024

Challenge 291

Middle Index

• Task 1: Middle Index

Task 1: Middle Index

Submitted by: Mohammad Sajid Anwar

---

You are given an array of integers, @ints.

Write a script to find the leftmost middle index (MI) i.e. the smallest amongst all the possible ones.

A middle index is an index where ints[0] + ints[1] + … + ints[MI-1] == ints[MI+1] + ints[MI+2] + … + ints[ints.length-1].

If MI == 0, the left side sum is considered to be 0. Similarly,
if MI == ints.length - 1, the right side sum is considered to be 0.

Return the leftmost MI that satisfies the condition, or -1 if there is no such index.

Example 1

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

The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4

Example 2

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

The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0

Example 3

Input: @ints = (2, 5)
Output: -1

There is no valid MI.

---

Solution

In the equation

ints[0] + ints[1] + … + ints[MI-1] ==
ints[MI+1] + ints[MI+2] + … + ints[ints.length-1]

we may add ints[MI] to both sides, i.e. we consider the middle index’s value as contained in both parts. This leads to a simplification, as we no longer need to handle MI == 0 and MI == ints.length - 1 specially because there are no empty parts any longer.

Using PDL we can calculate the forward and reverse cumulative sums over the integers and find the first index were both are equal.

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

sub middle_index {
    my $i = long @_;
    my $mi = which $i->cumusumover == $i(-1:0)->cumusumover->(-1:0);

    $mi->isempty ? -1 : $mi((0));
}

See the full solution to task 1.

---

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.