Hey everyone, I'm pretty new to binary searching, and I would really appreciate some help with this problem. I initially started trying to solve this problem last week, and I still haven't solved it!

Here's the problem: "Given an array A of N (1 <= N <= 100,000) positive integers, is it's possible to remove exactly two elements in the array to form a partition of the array into three continuous sub-arrays 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.

The solution (thanks to apostoldaniel854) is as follows:

Compute the prefix array of the array A so that we can do range-querying in O(1). Now let i, j be the indices of the elements that we're going to remove. If we fix i so that our first sub-array is A[0...i-1], we know that the other two subarrays need to have sum equal to prefix[i — 1]. In order to see if this is possible, we can search for the first position of j such that sum[1...i-1] <= sum[i+1...j-1] using binary search. If sum[1...i-1] != sum[i+1...j-1], then we can't get a partition of the original array with the selected value of i. Otherwise, we need to look at sum[j + 1...n] in order to see if it's equal to the other two sums. If it is, we've found a valid partition.

In theory this solution makes perfect sense to me. But, implementing it is a completely different story. I was wondering whether someone could please help me with this implementation -- I've been struggling with it for quite a long time now.

Here is what I have right now:

int main() {
	vector<int> A = {1, 3, 4, 2, 2, 2, 1, 1, 2};

	vector<int> prefix;
	prefix.push_back(A[0]);
        
	FOR(i, 1, A.size()) {
		prefix.push_back(prefix[i - 1] + A[i]);
	}

	/* Let i, j be the indexes of the element we are going to remove. */
	FOR(i, 1, A.size() - 3) {
		int sum_of_subarray_one = prefix[i - 1];

		/* Now we want to find the first position j so that
		 * sum[1...i-1] <= sum[i+1...j-1] with binary search. */
	}

	return 0;
}

I'm really just struggling with the part where we need to do a binary search. I can bruteforce the value of j with another for-loop, but that gives me an O(n^2) time complexity. With binary search, I would be able to get O(nlogn). I would greatly appreciate anyone's help in this problem. It seems like whenever I try one thing, another problem arises somewhere else :)