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.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Please credit the original source of the problem. $\endgroup$
    – John L.
    Dec 23, 2018 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, 2018 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, 2018 at 7:24
  • $\begingroup$ @BlackArrow, I posted an O(n^2) method $\endgroup$
    – James Waldby - jwpat7
    Jun 16, 2019 at 20:08
  • $\begingroup$ What is to be the output? Assuming non-empty from both ends of the array, I'd greedily sum from whatever end has the lower partial sum until equal or impossible. $\endgroup$
    – greybeard
    Nov 8, 2020 at 8:04

1 Answer 1

Reset to default
1
$\begingroup$

Let S denote the solution sum. Besides the trivial O(1) solution with S=0, other solutions if any can be found by an easy O(n2) method. Let A denote a given array of positive integers. Consider two kinds of partitions of A: (B, C, E, D) and (F, E, G, H), where each letter represents a sequential part of A, with A=B+C+E+D or A=F+E+G+H; C or G possibly empty; with E representing the extracted sequence. We suppose a solution has either S = sum(B) = sum(C+D) = (sum(A)-sum(E))/2 or S = sum(F+G) = sum(H) = (sum(A)-sum(E))/2, and claim that any solution has either an intact prefix or an intact suffix, or both, uninterrupted by extraction E.

To test for a solution of the first kind: Let S be a prefix sum of A. We look for a solution for S by advancing the beginning of E through A, and after each advance, solving (at O(1) amortized cost) for the end of E. With O(n) prefix sums and O(n) beginnings-of-E, overall cost is O(n2).

Testing for solutions of the second kind is analogous. The lightly-tested program shown below does this step by testing reversed(A).

#!/usr/bin/env python3
# Program written by James Waldby on 16 June 2019
# re: https://cs.stackexchange.com/questions/101950,
# "Array subset division with equal sums"
# Copyright © 2019 by James Waldby.  Offered without warranty under
# GPL v3 terms as at http://www.gnu.org/licenses/gpl.html

def findPrefixSol(A):
    S=0; U=sum(A); H=U//2; n=len(A); print (A)
    for i in range(n):        # prefix = first i elements
        S += A[i]
        if S>H: break
        Esum = 0                # sum of extract E
        Etarget = U - 2*S       # required size of E
        k = i+1                 # k -> after last element of E
        for j in range(i+1, n-1): # j -> first element of E
            while Esum < Etarget and k<n-1:
                Esum += A[k]
                k += 1
            if Esum > Etarget:
                Esum -= A[j]    # remove first element of E
                continue        # go try next E
            if Esum < Etarget:
                break           # can't extract enough to win; advance i
            print('Sol. for partition {}...{}...:  S={}, Es={}, U={}'.format(A[:i+1], A[j:k], S, Esum, U))
            break

A=[7, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
print()
A=[7, 5, 9, 1, 5, 9, 1, 3, 9, 9, 1, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Because no negative numbers are present, a contiguous subsequence beginning at or to the right of some position $j$ and summing to a given value $T$ can be found in $O(n)$ time: Whenever we go over the total, at $\Sigma [j, k) > T$, say, we move the left edge to $j+1$ but we don't need to wind the right edge $k$ all the way back to $j+1$: It must have been that $\Sigma [j, k-1) < T$, since otherwise we would have never incremented $k$ to reach $[j, k)$. Since $\Sigma [j, k-1) < T$ and all numbers are positive, then certainly $\Sigma [j+1, k-1) < T$ too, so it's safe to start from there. $\endgroup$
    – j_random_hacker
    Nov 8, 2020 at 18:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.