Introduction

Tape Equilibrium is a problem often encountered in algorithmic training, notably featured on platforms such as Codility, which is known for its lessons and challenges designed to hone programming and algorithm development skills. The essence of this problem lies in finding an equilibrium point in an array, a task that on the surface appears deceptively simple but teaches fundamental concepts of array manipulation and optimization.

Problem Statement

The problem can be briefly stated as follows:

Given a non-empty array `A` consisting of `N` integers, find the minimum absolute difference between the sum of the first part and the second part of the array after splitting the tape at an index `P` where `0 < P < N`.

Technical Explanation

This task requires calculating the difference between the two parts of the array created by the split, and it aims to find the minimum possible absolute difference.

Key Ideas and Approach

1. Prefix Sums: Before directly trying to solve the problem, one should compute the total sum of the array. This helps in avoiding recalculating sums repeatedly. Instead, with the prefix sum of indices up to `P`, one can derive the sum of the elements beyond `P`.
2. Iterative Difference Calculation: Iterate over possible split points from `1` to `N-1`. For each position:
   • Calculate the sum of elements from the start of the array up to `P` (prefix sum).
   • Derive the sum of the elements from `P` to the end of the array using the total sum.
   • Compute the absolute difference and update the minimum difference found.
3. Time Complexity:
   • Constructing the prefix sum is done in `O(N)`.
   • Calculating the difference for each possible split involves constant-time operations, leading to an overall complexity of `O(N)`.

Example

Consider `A = [3, 1, 2, 4, 3]`.

• Total sum, `S = 13`
• Possible splits and differences:
  • Split at 1: First part = 3, Second part = 10, Difference = `|3 - 10| = 7`
  • Split at 2: First part = 4, Second part = 9, Difference = `|4 - 9| = 5`
  • Split at 3: First part = 6, Second part = 7, Difference = `|6 - 7| = 1`
  • Split at 4: First part = 10, Second part = 3, Difference = `|10 - 3| = 7`

The minimum difference is `1`, achieved by splitting after the third element.

Pseudocode