TapeEquilibrium - codility - JavaScript

Question

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:

function solution(A);

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.

Write an efficient algorithm for the following assumptions:

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

My solution:

A = []
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)

  if (A.length > 0) {
    let defArr = [];
    let l = [];
    let all = A.reduce((a, b) => {
      l.push(a)
      return a + b
    })

    l.forEach((item) => {
      defArr.push(Math.abs(all - (item + item)))
    })
    return Math.min(...defArr)
  }

  return 0;

}
console.log(solution(A))

Answer 1

Logically, the code looks correct but from performance perspective, there are few things that can be improved. Let's look at the 2 points:

• Time Complexity: O(n) - 1 loop, 1 reduce and 1 Math.min. All run in O(n) time.
• Space Complexity: O(n) - Two arrays - defArr and l which have size n

There is nothing can be done for time complexity but space complexity can be reduced to constant space. No need to have additional arrays. One can simply loop and store intermediate values in temporary variables.

I have re-written the same. Inside the loop, at each index, the difference is calculated and compared to a min variable. If the new min is lesser than existing one; then update min otherwise do next iteration.

A = []
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

function solution(A) {
  let sum = A.reduce((total, value) => total + value, 0)
  let min = Number.POSITIVE_INFINITY
  let cumulativeSum = 0
  for (let i = 0; i < A.length - 1; ++i) {
    cumulativeSum = cumulativeSum + A[i]
    sum = sum - A[i]
    diff = Math.abs(sum - cumulativeSum)
    if (diff < min) {
      min = diff
    }
  }
  return min
}

console.log(solution(A))

Hope it helps. Revert for any doubts/clarifications.

Answer 2

Not sure how much if affects performance (haven't measured), but one could return the solution in a couple of edge cases without going into the for loop every time:

function solution(A) {
    // If there are only two items in the array, return their difference
    if (A.length === 2) Math.abs(A[0] - A[1]);

    // If every item in the array is the same
    if (A.every((item) => item === A[0])) {
        // If length is even, return zero, else return the item as that will be the difference
        (A.length % 2) === 0 ? 0 : A[0];
    }

    // ... rest of the solution from the accepted answer above

}