Peter
Peter Campbell Smith

Four is magic and
equilibrium indices

Weekly challenge 160 — 11 April 2022

Week 160: 11 Apr 2022

Task 2

Task — Equilibrium index

You are give an array of integers, @n. Write a script to find out the equilibrium index of the given array, if found.

For an array A consisting n elements, index i is an equilibrium index if the sum of elements of subarray A[0…i-1] is equal to the sum of elements of subarray A[i+1…n-1].

Examples


Example 1:
Input: @n = (1, 3, 5, 7, 9)
Output: 3


Example 2:
Input: @n = (1, 2, 3, 4, 5)
Output: -1 as no equilibrium index found.


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

Analysis

If we were guaranteed that the numbers were sorted in ascending order we could do a binary chop to get to the answer, but we're not, so I can see little alternative to starting at the second member of the array and working through to the second last. It's the second, because the statement of the problem suggests that the two subarrays are not null.

I suppose you save a few nanoseconds by doing something like this:

$left_sum = $array[0];
$right_sum = sum of $array[2] to the end;

and then loop over the array elements, adding the element to $left_sum, and subtracting it from $right_sum, but really, that's a bit messy and for any reasonable array it won't take long just to recreate $left_sum and $right_sum each time. So that's what I did.

I noted that It doesn't say positive or non-zero integers, so we'd better allow for zero and negative ones, which means that there may not be a unique answer (eg 4, 5, 0, 0, 4, 5 or -3, 3, 0, -4, 4, 0, -5, 5).

Try it 

Try running the script with any input:



example: 1, 3, 5, 7, 9

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-03-30
# PWC 158 task 1

use v5.28;
use strict;
use warnings;
use utf8;

my (@tests, $test, $last, $try, $left, $right, $j, %tried, $string);

@tests = ([1, 3, 5, 7, 9],
          [1, 2, 3, 4, 5],
          [2, 4, 2], 
          [1, 2, 3, 4, 5, 6, 0, 21],
          [14, -12, -26, 7, -24],
          [15, 1, 5, 5, 5], 
          [5, 5, 5, 1, 15], 
          [3, -3, 8], 
          [4, 5, 0, 0, 4, 5], 
          [-3, 3, 0, -4, 4, 0, -5, 5]);

for $test (@tests) {
    
    # format input
    $string = qq[\nInput:  (];
    for $j (@$test) {
        $string .= qq[$j, ];
    }
    say substr($string, 0, -2) . ')';
    
    # check every possibility (see comments at top)
    $last = scalar @$test;
    for $j (1 .. $last - 2) {
        $left = sum_of($test, 0, $j - 1);
        $right = sum_of($test, $j + 1, $last - 1);
        
        # found an answer
        if ($left == $right) {
            say qq[Output: $j];
            last;
        }
    }
    
    # no EI found
    say qq[Output: -1 as no Equilibrium Index found] unless $left == $right;
}
    
sub sum_of {
    
    # returns sum of $array[$left] .. $array[$right]
    my ($array, $left, $right) = @_;
    my ($j, $sum);
    $sum = 0;
    for $j ($left .. $right) {
        $sum += $array->[$j];
    }
    return $sum;
}
    

Output


Input:  (1, 3, 5, 7, 9)
Output: 3

Input:  (1, 2, 3, 4, 5)
Output: -1 as no Equilibrium Index found

Input:  (2, 4, 2)
Output: 1

Input:  (1, 2, 3, 4, 5, 6, 0, 21)
Output: 6

Input:  (14, -12, -26, 7, -24)
Output: 3

Input:  (15, 1, 5, 5, 5)
Output: 1

Input:  (5, 5, 5, 1, 15)
Output: 3

Input:  (3, -3, 8)
Output: -1 as no Equilibrium Index found

Input:  (4, 5, 0, 0, 4, 5)
Output: 2

Input:  (-3, 3, 0, -4, 4, 0, -5, 5)
Output: 2

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain