HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Tape Equilibrium O(n)

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
tapeequilibriumstackoverflow

Problem

Problem (Tape Equilibrium):


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.

My solution to it is:

class Solution {
    public int solution(int[] A) {
        long minDiff = Integer.MAX_VALUE;
        long[] leftSums = new long[A.length];
        long totalSum = 0;

        //init
        totalSum += A[0];
        leftSums[0] += 0;  //whatever, don't use leftSums[0] anyway

        for (int i = 1; i < A.length; ++i) {
            totalSum += A[i];
            leftSums[i] += leftSums[i-1] + A[i-1];
        }

        for (int i = 1; i < A.length; ++i) {
            long diff = Math.abs(totalSum - 2 * leftSums[i]);
            if(diff < minDiff){
                minDiff = diff;
            }
        }

        return (int) minDiff;
    }
}

Solution

Correctness

I assume this is a toy problem and you don't need to worry about overflow/underflow? If you do, you should be using longs to do all your math, and either returning a long or casting back to an int before you return it.
Performance

You don't need to keep an array of all the left sums. You can get away with just two ints, one containing the sum of numbers on the left and the other containing the sum of numbers on the right. In your second loop, look at the ith element. Add it to the leftSum and subtract it from the rightSum. Use that to do your math.
General

This also cleans up the math you're doing. totalSum - 2 * leftSums[i] is not at all intuitive. Using Math.abs is nice. Using Math.min() would be even nicer.

Java variables start with lowercase letters. int[] A doesn't conform to that standard. Also, abbreviations should be avoided in variable names. minDiff would be better as minimumDifference, and diff would be better as difference.

If I were to code this, it would look something like:

public final class Summer {

    public int solve(final int[] values) {

        long leftSum = 0;
        long rightSum = 0;
        for (int i = 0; i < values.length; i++) {
            rightSum += values[i];
        }

        long minDifference = Integer.MAX_VALUE;
        for (int i = 0; i < values.length; i++) {
            leftSum += values[i];
            rightSum -= values[i];
            final long difference = Math.abs(leftSum - rightSum);
            minDifference = Math.min(minDifference, difference);
        }

        return (int) minDifference;
    }
}

Code Snippets

public final class Summer {

    public int solve(final int[] values) {

        long leftSum = 0;
        long rightSum = 0;
        for (int i = 0; i < values.length; i++) {
            rightSum += values[i];
        }

        long minDifference = Integer.MAX_VALUE;
        for (int i = 0; i < values.length; i++) {
            leftSum += values[i];
            rightSum -= values[i];
            final long difference = Math.abs(leftSum - rightSum);
            minDifference = Math.min(minDifference, difference);
        }

        return (int) minDifference;
    }
}

Context

StackExchange Code Review Q#111328, answer score: 4

Revisions (0)

No revisions yet.