Telemetry task "TapeEquilibrium"
I solved the first problem in code (TapeEquilibrium).
I managed to get a 50% score (100% correctness, 0% performance).
Can you give me some tips on how to improve performance.
A link to my results and a description of the problem is here .
Code below:
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> splittedTape = new ArrayList<Integer>();
for (int i = 1; i < A.length; i++){
splittedTape.add(calculateDifference(i, A));
}
Collections.sort(splittedTape);
return splittedTape.get(0);
}
private int calculateDifference(int position, int[] array){
int sumA = 0;
int sumB = 0;
for (int i = 0; i < array.length; i++){
if (i < position){
sumA += array[i];
} else {
sumB += array[i];
}
}
return Math.abs(sumA - sumB);
}
}
Thanks in advance.
+3
source to share
3 answers
I haven't quite tested the corner cases, so this may not give the expected results, but this is an O (N) solution to achieve what the problem is asking.
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int totalSum = 0;
int firstSum = A[0];
for(int i=1;i<A.length;i++)
totalSum += A[i];
int min = Math.abs(firstSum-totalSum);
for(int i=1;i<A.length-1;i++) {
firstSum+=A[i];
totalSum-=A[i];
if(Math.abs(firstSum-totalSum)<min)
min = Math.abs(firstSum-totalSum);
}
return min;
}
}
+3
source to share
The following Java solution gives 100% O (n) complexity.
public static int solution(int[] A) {
int accumulator = 0;
int originalArrayLength = A.length;
int[] accumulatedArray = new int[originalArrayLength];
for (int i = 0; i < originalArrayLength; i++) {
accumulator += A[i];
accumulatedArray[i] = accumulator;
}
int max = accumulatedArray[originalArrayLength - 1];
int minAbsoluteDiff = Integer.MAX_VALUE;
for (int i = 0; i < accumulatedArray.length - 1; i++) {
int firstSum = accumulatedArray[i];
int secondSum = max - firstSum;
int absoluteDiff = Math.abs(firstSum - secondSum);
if (absoluteDiff < minAbsoluteDiff) {
minAbsoluteDiff = absoluteDiff;
}
}
0
source to share
The code is a little easier to understand:
class Solution {
public int solution(int[] numbersOnATape) {
int minimalDifference = Integer.MAX_VALUE;
int sumOfFirstPart = 0;
int sumOfSecondPart = sumOfValuesInsideOfTheTap(numbersOnATape);
for (int count = 0; count < numbersOnATape.length - 1; count++) {
int currentNumber = numbersOnATape[count];
int nextNumber = numbersOnATape[count + 1];
sumOfFirstPart += currentNumber;
int difference = Math.abs(sumOfFirstPart - sumOfSecondPart);
if (minimalDifference > difference) {
minimalDifference = difference;
}
sumOfSecondPart -= nextNumber;
}
return minimalDifference;
}
private int sumOfValuesInsideOfTheTap(int[] numbersOnATape) {
int sumOfValuesInsideOfTheTap = 0;
for (int count = 1; count < numbersOnATape.length; count++) {
sumOfValuesInsideOfTheTap += numbersOnATape[count];
}
return sumOfValuesInsideOfTheTap;
}
}
one hundred%
0
source to share