• 113k
• 15
• 154
• 396

• 41.7k
• 7
• 70
• 134

• 21
• 1

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])|

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 O(N);
 expected worst-case space complexity is 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));
 }
 }
 }
}