Codility 1. TapeEquilibrium

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:

class Solution { public int solution(int[] 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].
Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

💡 풀이

1. 시간 복잡도를 고려해서, O(N) 만에 갈 수 있는 방법을 고민해야 한다. N의 제곱으로는 10억번의 연산을 해야하므로 시간초과가 발생할 것이다.
2. left sum 과 right sum 을 더하면 total 이 될 것이므로, left 하나만 구하면 right 는 자동으로 계산이 된다.
3. left_sum 도 이전에 계산해 놓은 값과 다음 인덱스만 더해주면 바로 구할수 있다.
4. 결과적으로 O(N) 의 시간이 걸리는 알고리즘을 구현할 수 있다.

📝 소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        int min = Integer.MAX_VALUE;

        int total_sum = 0;
        for(int i = 0; i < A.length; i++) {
            total_sum += A[i];
        }
        int left_sum = 0;
        int right_sum = 0;
        
        for(int P = 1; P < A.length; P++) {
            left_sum += A[P-1];
            right_sum = total_sum - left_sum;

            min = Math.min(Math.abs(left_sum - right_sum), min);
        }
        return min;
    }
}