patternjavaMinor
Tape Equilibrium O(n)
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
splits this tape into two non−empty parts:
The difference between the two parts is the value of:
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:
We can split this tape in four places:
Write a function:
non-empty zero-indexed array A of N integers, returns the minimal
difference that can be achieved.
My solution to it is:
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] = 3We 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| = 7Write a function:
int solution(int A[], int N); that, given anon-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
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
General
This also cleans up the math you're doing.
Java variables start with lowercase letters.
If I were to code this, it would look something like:
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.