1
$\begingroup$

Today I stumbled upon a problem which looked like the partition problem but certainly is different.

Given array of positive integers, guaranteed to not be divisible into two continious subsets of equal sum, remove a ceratin continious subset to form two subsets of equal sum.

Example:

  • Array: 7 5 9 1 3 9 6
  • Remove elements 9 and 1 to form array 7 5 3 9 6 that is divisible into two subarrays of equal sum {7,5,3} and {9,6}

Another example:

  • Array: 1 10 100
  • Whichever subset to remove in the second case, it is not possible to split the array into two parts with the same sum.

The limits for the array are 8000 elements and each element can be 1 bilion in size.

I'am just looking for algorithm help as I thought this was a variation of the partition problem and tried for some time to solve it, but i figured out it's beyond my knowledge. Any kind of help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Please credit the original source of the problem. $\endgroup$ – Apass.Jack Dec 23 '18 at 2:53
  • $\begingroup$ The "continuous subsets" part is definitely helpful, since we have to consider only a polynomial (in terms of n) number of possibilities. $\endgroup$ – Gassa Dec 23 '18 at 16:16
  • $\begingroup$ Because there are O(n^2) possibles continuous subset (subsequence?) and we could find the "separating point" of the two equal sum subsets in O(n), we have a trivial O(n^3) solution. We could reduce the second part to O(lg n) with binary search and prefix sum. Not sure that a O(n^2 lg n) would be enough. Use 64-bit deal with the 1 billion upper bound. $\endgroup$ – Black Arrow Dec 25 '18 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.