0

I have this function that returns the minimum difference between the sum of two parts of an array based on the position P the Array is partitioned. The programmed is tested to to run at O(N * N) time complexity and 0% performance though O(N) is was expected.

Question: Is there any aspect of this I can change to improve on the performance? Is there a better way to summing array within a loop without using a sub-loop? Thanks

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

https://jsbin.com/mehisi/edit 

function solution(A) {

  'use strict';

  if(arguments.length === 1 && typeof A === "object" && A.length > 1 ){
    try{
      const N = A.length;

      let diff;
      for( let P =1 ; P < N ; P++) {
        // For each value of P, calc the difference 
        //|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

        // use slice to prevent modification of oraginal copy
        var A2 = A.slice(0) ; 
        //splice array into two A1 and A2
        let A1 = A2.splice(0, P);  // All Element from start up to P
        console.log("From Array " + A  + " Remove "+ A1 + " Remaining " + A2);
        // reduce((a, b) => a + b, 0); 
        let diffp = Math.abs((A1.reduce(function(a, b) { return a + b; }, 0)) - 
            (A2.reduce(function(a, b) { return a + b; }, 0))) ;

        if(diff > diffp || diff === undefined ){
          diff = diffp ;
        }
        console.log(P + "Difference ="+ diff + " Instead of " + diffp + " \r\n " );
      }

      // Return the Minimum value of P
      return diff  ;
    }
    catch(err){
     console.log("Error: " + err );
    return 0 ; // undefined ;
    }
  }else{
     console.log("Invalid parameter(s)");
    return 0 ; // undefined ;
  }

}

var A = [] ;
  A[0] = 5
  A[1] = 1
  A[2] = 2
  A[3] = 7
  A[4] = 4
console.log(solution(A)) ;
Nditah
  • 1,429
  • 19
  • 23

1 Answers1

1

Yes, it's pretty trivial to do this in linear time (and even constant space) with a running sum.

function solution(arr) {
    var leftSum = 0; // sum from 0 to P
    var rightSum = arr.reduce((a, b) => a + b, 0); // sum from P to N
    var min = Math.abs(leftSum - rightSum); // initial value for p=0
    for (var p = 0; p < arr.length; p++)
        // move the element from the right to the left side
        leftSum += arr[p];
        rightSum -= arr[p];
        // then update minimum difference
        min = Math.min(min, Math.abs(leftSum - rightSum));
    }
    return min;
}
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • 100% Performance with O(N) time complexity. Thank you very much @Bergi. – Nditah Mar 03 '18 at 19:10
  • Just for the record, the solution given with the question was rated 100% Correctness, 0% performance, while this one is 66% Correctness and 100% performance. Thus, this solution meets my desire since my question was on performance primarily. – Nditah Mar 03 '18 at 19:33
  • @Nditah It's missing out on correctness? What doesn't work? – Bergi Mar 03 '18 at 20:43
  • Sir, the truth is, I don't know exactly, but if you submit it here, given your expertise, I'm certain you would be able to interpret the code analysis. https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ – Nditah Mar 03 '18 at 22:19
  • I didn't submit anything, but I guess the difference is that I'm partitioning at all 0 <= P <= N, including empty snips. Should be simple to fix. – Bergi Mar 04 '18 at 11:19
  • Sir I didn't understand what you mean by partitioning at all 0 <= P <= N, Sir. – Nditah Mar 04 '18 at 11:36
  • The tape is split at position P. My code tries all positions, including 0 and N, so that it works for empty tapes as well, but the exercise does not consider these. – Bergi Mar 04 '18 at 11:59