##### Short Problem Definition:

Minimize the value |(A[0] + … + A[P-1]) – (A[P] + … + A[N-1])|.

##### Link

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

##### Execution:

In the first run I compute the left part up to the point i and the overall sum *last*. Then I compute the minimal difference between 0..i and i+1..n.

##### Solution:

import sys def solution(A): #1st pass parts = [0] * len(A) parts[0] = A[0] for idx in xrange(1, len(A)): parts[idx] = A[idx] + parts[idx-1] #2nd pass solution = sys.maxint for idx in xrange(0, len(parts)-1): solution = min(solution,abs(parts[-1] - 2 * parts[idx])); return solution

#include <algorithm> #include <climits> int solution(vector<int> &A) { unsigned int size = A.size(); vector<long long> parts; parts.reserve(size+1); long long last = 0; for (unsigned int i=0; i<size-1; i++){ if (i == 0){ parts.push_back(A[i]); } else { parts.push_back(A[i]+parts[i-1]); } if (i==size-2){ last = parts[i]+ A[i+1]; } } long long solution = LLONG_MAX; for(unsigned int i=0; i<parts.size(); i++){ solution = min(solution,abs(last - 2 * parts[i])); } return solution; }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.