[JAVA] [100%] TapeEquilibrium (src & jUnit)

Painless

TapeEquilibrium

Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.

Task description

Given a non-empty array A consisting of N integers. Array A represents the numbers on the tape.

Any integer P, such as 0 <P <N, divides 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 following values:|（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 the following array A:

  A [0] = 3
  A [1] = 1
  A [2] = 2
  A [3] = 4
  A [4] = 3

This tape can be split into four parts.

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）; }

This returns the smallest difference that can be achieved given a non-empty array A of N integers.

For example:

  A [0] = 3
  A [1] = 1
  A [2] = 2
  A [3] = 4
  A [4] = 3

As explained above, the function must return 1.

Write an efficient algorithm for the following assumptions:

• N is an integer in the range [2..100,000].
• Each element of array A is an integer in the range [-1,000..1,000].

solve

Program TapeEquilibriumSolution.java

TapeEquilibriumSolution.java

    public int solution(int[] A) {
        int difference = 0;
        int sumPart1 = 0;
        int sumPart2 = 0;
        int sum = 0;

        for (int i = 0; i < A.length; i++) {
            sum += A[i];
        }

        sumPart1 = A[0];
        sumPart2 = sum - sumPart1;
        difference = Math.abs(sumPart1 - sumPart2);
        for (int p = 2; p < A.length; p++) {
            sumPart1 += A[p - 1];
            sumPart2 -= A[p - 1];
            int temp = Math.abs(sumPart1 - sumPart2);
            if (temp < difference) {
                difference = temp;
            }
        }

        return difference;
    }

Detected time complexity:
O(N)

jUnit PermCheckSolutionTest.java

Report Candidate Report: trainingAVSN2R-5SF