CODEWITHSUNDEEP
arraysalgorithmbig-o
NNNNNNNNNNDelicious
NNNNNNNNNNDelicious

Reputation: 983

Finding the position to cut an array in half, such that the difference of the sums is minimal

I'm doing some practice programming problems to prepare for an interview.

One of these questions follows: you are attempting to find the place to cut an array in half, such that the difference between the sums of each half is minimized. What is the minimal difference that can be achieved?

So

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

So we would return 1, since that is the minimal difference.

This is easy enough to do in n squared time, however the problem specifies it can be done in n time, with n storage space. Can anyone recommend a solution? Every way I look at it you'd have to keep running along the array even with the extra space. You need to know the value of the whole array before you can make a choice which cut would be minimal.

Upvotes: 2

Views: 121

Answers (2)

Dijkgraaf
Dijkgraaf

Reputation: 11527

Have two running sums, one starting at position 0 the other at N.

Initialise the sum from the starting positions.

Compare the two sums, if the first is smaller or equal one advance the position of the cursor for the first sum upwards, otherwise advance the position of the second sum cursor downwards.

Check to see that you haven't reached the cursor position of the other sum. If you have, exit the loop and you have your sums and you can subtract them to get the minimal difference.

If not add the new value from the new position to the appropriate sum and loop.

Upvotes: 2

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521209

It is possible to find the middle cut position by making two O(n) passes. Consider your original problem:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

Iterate over this array of values and record the incremental sum in a new array called sums:

sums[0] = 3
sums[1] = 4
sums[2] = 6
sums[3] = 10
sums[4] = 13

After this iteration, you also know what the total sum is, which in this case is 13. Now all you need to do is walk through the sums array and choose the value which is closest to half the sum. In this case, sums[2] = 6 fits the bill, so you would make the cut in the third position.

sums[0] = 3
sums[1] = 4
sums[2] = 6
-----------      <-- make the cut here
sums[3] = 10
sums[4] = 13

Upvotes: 5

Related Questions