I was wondering if anyone knows how to solve the following question. I have tried on-and-off for about a week now, but I cannot figure it out:
Given an array A of N (1 <= N <= 100,000) positive integers, is it possible to remove exactly two elements in the array in order to form a partition of the array into three contiguous subarrays with equal sums?
For example, if A = [1, 3, 4, 2, 2, 2, 1, 1, 2], you can remove the "4" and the second-to-last "2" in order to get the following array: A = [1, 3, REMOVED, 2, 2, REMOVED, 1, 1, 2].
This works because 1 + 3 = 2 + 2 = 1 + 1 + 2 = 4.
But in some cases it might not be possible. For instance, if A = [1, 1, 1, 1, 1, 1], it's impossible,
Something important to keep note of is that don't need to determine which elements to remove but rather whether or not it is possible (so just yes/no is enough).
I have been struggling for a really long time with this problem. It is a variant of the "partition an array into 3 parts with equal sums" problem since you're forced to drop two elements in the array here.
I have tried thinking of DP solutions with no luck. Does anyone know how I can solve this? I think prefix sums might be useful here.
Let
i
andj
be the indexes of the elements that we are gonna remove.Well, if we fix
i
than we know how much we want the other 2 sums to be. Let's look for the first positionj
so thatsum[1...i-1] <= sum[i+1...j-1]
. We can do that easily by binary search. Ifsum[1...i-1] != sum[i+1...j-1]
then we can't get a partition if we remove the ith element, else we need to look atsum[j+1...n]
to see if it is equal to the other 2 sums. If it is then we've found a valid partition.Of course, so we can access the sums in
O(1)
we are gonna use prefix sums.If the elements of the array are non-negative than there's some more case work to do, but in this case if they are
>0
, I think this solution is right.Hey, thank you a lot for your help. This makes sense to me in theory, and you are correct that all of the integers are positive (so there shouldn't be any special cases). However, I am having a lot of trouble actually implementing this as practice. I was wondering whether you would be able to take a look at my code, and help me. I have added comments so that you understand what I am trying to do. In particular, I am having a lot of trouble setting up the binary search part, and the portions after it.
I would really appreciate any help.
Hey, thank you for posting an interesting question.
So instead of finding a
j
such thatsum[1...i-1] <= sum[i+1...j-1]
i directly wrote binary search to returnj
such thatsum[0...i-1] == sum[i+1...j]
if there exists one or else return-1
.(my indexing starts from 0)here
sum_one
is the sum of the first subarray anddiff
is the sum upto the first element we removed. So if we remove element at indexi
thensum_one = sum[i-1]
anddiff = sum[i]
.