TapeEquilibrium, Solution Failing Two Edge Cases

Tags: ,



Currently working on problems from codility for practice, and for some reason I’m unable to get more than 83% correctness overall, originally I solved it with 100% correctness but with N^2 time complexity (it needs to be N or lower)

I’ve adjusted my code to be able to solve in O(N) but now my correctness has dropped to 77%, I’m currently trying to solve for cases of 2 elements ie) [1000,-1000] should return 2000, but I return a 0;

Link to Question on Codility:https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

The question:

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.

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]

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int pval = Integer.MAX_VALUE;
        int sum = 0;
        int pone = 0;
        int ptwo = 0;
        int currdiff = 0;
        for(int i = 0; i<A.length; i++ ){
            sum += A[i];
        }
        
        ptwo = sum;
        for(int j = 0; j< A.length; j++){
            pone += A[j];
            ptwo -= A[j];
            currdiff = Math.abs(ptwo - pone);
            if(currdiff < pval)
                pval = currdiff;
        }
        return pval;
    }
}

Answer

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts

The “non-empty” is crucial here. If you would try printing both parts in the second loop you would see that in the last iteration the second part is empty.

All you need to do is skip the last iteration in you loop:

public int solution(int[] A) {
    int pval = Integer.MAX_VALUE;
    int sum = 0;
    int pone = 0;
    int ptwo = 0;
    int currdiff = 0;
    for(int i = 0; i<A.length; i++ ){
        sum += A[i];
    }
    
    ptwo = sum;
    for(int j = 0; j< A.length-1; j++){ //<- notice -1 here
        pone += A[j];
        ptwo -= A[j];
        currdiff = Math.abs(ptwo - pone);
        if(currdiff < pval)
            pval = currdiff;
    }
    return pval;
}


Source: stackoverflow