Find minimum distance

[frek]

A non-empty 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] = 3
We 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| = 7
Write a function:

int solution(vector<int> &A);

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].

O(N)

#include <numeric>
#include <cmath>
#include <cstdlib>

int solution(vector<int> &A) {
    auto sum = std::accumulate(A.begin(), A.end(), 0ll);
	long long leftPart{ A[0] };
	long long minDiff{ std::abs(2 * leftPart - sum) };

	for (int i = 1; i < A.size() - 1; ++i) {
		leftPart += A[i];
		minDiff = std::abs(2 * leftPart - sum) < minDiff ? std::abs(2 * leftPart - sum) : minDiff;
	}
	return minDiff;
}

Comments, please?

[lastchance]

frek wrote:

Comments, please?

- Looks like it works and is O(N)
- You could return early if you found a difference of 0
- You could store the current difference, rather than the current left part, if you wanted to.

#include <iostream>
#include <cstdlib>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

int solution( const vector<int> &A )
{
   long long sum = accumulate( A.begin(), A.end(), 0ll );
   long long diff = sum - 2 * A[0], mindiff = abs( diff );
   for ( int i = 1; i < A.size() - 1; i++ )
   {
      diff -= 2 * A[i];
      if ( diff == 0 ) return 0;
      mindiff = min( mindiff, abs( diff ) );
   }
   return mindiff;
}

int main()
{
   vector< vector<int> > tests = { { 3, 1, 2, 4, 3 }, { -1, 2, -3, 4, -5, 6 } };
   for ( auto &V : tests ) cout << solution( V ) << '\n';
}

[frek]

> Looks like it works and is O(N)

How to you measure the correctness and time complexity of it, please? Do you do it manually or use a tool?

>for ( int i = 1; i < A.size() - 1; i++ )

Do you normally compare signed types with unsigned ones?
I assume I should have used for ( size_t i = 1; i < A.size() - 1; i++ )

[lastchance]

How to measure the "correctness"? Well, just do your level best to "prove" the method outside of code and then subject it to lots of tests. (Dreaming up a comprehensive set of tests, that include all "edge" cases, is quite hard in itself. I've left the basic assumption that A has 2 elements at least here.)

I don't "measure" the time complexity - I just inspect the algorithm. Usually, I refer to a few known cases: straight traversal O(N); nested loops O(N^2); sorting O(N log N) usually; setting up a tree, set or map O(N log N).

I prefer a minimum set of data types (I have a long background in Fortran!). So, I simply put up with the warning about signed and unsigned types when I know my indices aren't negative. Many languages don't have unsigned types and I don't particularly like them. You can't subtract them both ways, for example. Sure, arrays (in c++) only have positive or zero indices, but that isn't universally true in other languages.