Four is magic and

equilibrium indices

Weekly challenge 160 — 11 April 2022

Week 160 - 11 Apr 2022

Task 2

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].

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

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).

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

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

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain