0
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Will the person that down voted this question please provide a comment explaining why. \$\endgroup\$ – pacmaninbw Mar 29 '20 at 15:37
  • 3
    \$\begingroup\$ I thought this is for code review, and I'm a junior on that field, So I'm looking for the experts reviewing my code. \$\endgroup\$ – Moamen Mar 30 '20 at 16:08
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your clarification. \$\endgroup\$ – Moamen Apr 7 '20 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.