TapeEquilibrium

Minimize the value |(A[0] + … + A[p – 1]) – (A[p] + … + A[n – 1])|
ℹ️ © Codility, 2009-2018

Problem

A non-empty array A consisting of n integers is given. Array A represents numbers on a tape.
Any integer p, such that 0 < p < n, splits this tape into two non-empty parts: A[0], A[1], …, A[p – 1] and A[p], A[p + 1], …, A[n – 1].
The difference between the two parts is the value of: |(A[0] + A[1] + … + A[p – 1]) – (A[p] + A[p + 1] + … + A[n − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that: A[0] = 3, A[1] = 1, A[2] = 2, A[3] = 4, A[4] = 3, we can split this tape in four places:
• p = 1, difference = |3 − 10| = 7;
• p = 2, difference = |4 − 9| = 5;
• p = 3, difference = |6 − 7| = 1;
• p = 4, difference = |10 − 3| = 7.

Write a function that, given a non-empty array A of n integers, returns the minimal difference that can be achieved.

For example, given: A[0] = 3, A[1] = 1, A[2] = 2, A[3] = 4, A[4] = 3, the function should return 1, as explained above.

Assume that:
• n is an integer within the range [2 … 100,000];
• each element of array A is an integer within the range [-1,000 … 1,000].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(n) (not counting the storage required for input arguments).

Solution

C#

using System;
class Solution {
  public int solution(int[] A) {
    int n = A.Length;
    int s = 0;
    foreach (int a in A) {
      s += a;
    }
    int r = 100000;
    int s1 = 0;
    for (int p = 1; p < n; p++) {
      s1 += A[p - 1];
      int s2 = s - s1;
      int t = Math.Abs(s1 - s2);
      if (t < r) {
        r = t;
      }
    }
    return r;
  }
}

Java

import java.lang.Math;
class Solution {
  public int solution(int[] A) {
    int n = A.length;
    int s = 0;
    for (int a : A) {
      s += a;
    }
    int r = 100000;
    int s1 = 0;
    for (int p = 1; p < n; p++) {
      s1 += A[p - 1];
      int s2 = s - s1;
      int t = Math.abs(s1 - s2);
      if (t < r) {
        r = t;
      }
    }
    return r;
  }
}

JavaScript

function solution(A) {
  let n = A.length;
  let s = 0;
  for (let i in A) {
    s += A[i];
  }
  let r = 100000;
  let s1 = 0;
  for (let p = 1; p < n; p++) {
    s1 += A[p - 1];
    let s2 = s - s1;
    let t = Math.abs(s1 - s2);
    if (t < r) {
      r = t;
    }
  }
  return r;
}

PHP

function solution($A) {
  $n = count($A);
  $s = 0;
  foreach ($A as $a) {
    $s += $a;
  }
  $r = 100000;
  $s1 = 0;
  for ($p = 1; $p < $n; $p++) {
    $s1 += $A[$p - 1];
    $s2 = $s - $s1;
    $t = abs($s1 - $s2);
    if ($t < $r) {
      $r = $t;
    }
  }
  return $r;
}