Codility: Tape Equilibrium | Sesame notes

Codility: Tape Equilibrium | Sesame notes
A non-empty zero-indexed 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:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
O(1) space:
The code below still scans the array twice, but do 
not waste the memory as above.

int solution(int A[], int N) {
    
    long sum = 0;
    
    int i;
    
    //get the sum of all the elements.
    for (i = 0; i < N; i++){
        sum += A[i];
    }
    
    //check it with the running sums
    long rsum = A[0];
    sum -= A[0];
    
    long dif  = abs(sum - rsum); 
    for (i = 1; i < N - 1; i++){
        rsum += A[i];
        sum  -= A[i];
        long tmp = abs(sum - rsum);
        if (tmp < dif){
            dif = tmp;
        }
    }
    
    return dif;
}
O(N) space:
http://codility-lessons.blogspot.com/2014/04/lesson-1-tapeequilibrium.html

int solution(int A[], int N) {

    //long is large enough for this problem.
    long sum = 0;  
    
    int i;    
    int *B = (int*)alloca(sizeof(int) * N);   

    //first, scan the elements from the tail to the head and
    //create an array of the running sums at the point    
    //(from the tail to the point).
    
    long runningSum = 0;    
    for (i = N - 1; i > 0; i--){        
        runningSum += A[i];        
        B[i] = runningSum;    
    }        
    
    //now, scan the array again, checking the difference.   
    runningSum = A[0];   
    long dif = abs(B[1] - runningSum);    
    
    for (i = 1; i < N - 1; i++){        
        runningSum += A[i];        
        long tmp = abs(B[i + 1] - runningSum);        
        if (tmp < dif){           
            dif = tmp;         
            
        }    
    }  
    
    return dif;
}

http://robbypelssers.blogspot.com/2014/01/code-puzzler-tape-equilibrium.html

    public static int solution(int[] A) {


 List<Integer> numbers = toList(A);


 int size = numbers.size();


 int sumLeft = numbers.get(0);


 int sumRight = sum(numbers.subList(1, size)); 


        int minDifference = Math.abs(sumLeft - sumRight);


        for (int i : numbers.subList(1, size -1)) {  


            sumLeft = sumLeft + i;


            sumRight = sumRight - i;


            int difference = Math.abs(sumLeft - sumRight);


            if (difference < minDifference) {


                minDifference = difference;


            }


        }


 return minDifference;


    }

 


    public static int sum(List<Integer> numbers) {


 int sumRight = 0;


 for (int i : numbers) {


  sumRight += i;


 }  


 return sumRight;


    }

Read full article from Codility: Tape Equilibrium | Sesame notes