A non-empty zero-indexed array
A
consisting ofN
integers is given. ArrayA
represents numbers on a tape.Any integer
P
, such that0 < P < N
, splits this tape into two non-empty parts:A[0], A[1], ..., A[P − 1]
andA[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])|
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.
Complexity:
- expected worst-case time complexity is \$\mathcal{O}(N)\$;
- expected worst-case space complexity is \$\mathcal{O}(N)\$, beyond input storage (not counting the storage required for input arguments).
Here is my code..
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TapeEquilibium {
public static void main(String[] args) {
int[] a = {3,1,2,4,3};
System.out.println(solution(a));
}
public static int solution(int[] A){
long totalSum = 0;
List<Holder> list = new ArrayList<TapeEquilibium.Holder>();
for(int i=0;i<A.length;i++){
totalSum = totalSum + A[i];
}
long start = A[0];
for(int i=1;i<A.length;i++){
Holder holder = new Holder(i,Math.abs((2*start)-totalSum));
list.add(holder);
start = start+A[i];
}
Collections.sort(list);
return (int)(list.get(0).sum);
}
static class Holder implements Comparable<Holder>{
int p;
long sum;
public Holder(int p, long sum){
this.p = p;
this.sum = sum;
}
public int compareTo(Holder o) {
if(this == o) return 0;
else{
return new Long(this.sum).compareTo(new Long(o.sum));
}
}
}
}