This is documentation for my solution to 466C - Number of Ways. Credit goes to Coding Hangover for the algorithm. This post will detail the approach here, as well as provide an example.

Problem Statement

Given an array arr, we are to compute the number of ways we can partition arr into 3 chunks where each chunk is contiguous. Further, the sum of the elements in each chunk must be the same.

Running Example

We will use the input array arr = [1 2 3 0 3] as a running example.

Naive Approach

My first approach to this problem was to pre-compute an array A which is a running sum of arr. That is,A[i] = sum(a[:i])` inclusive. Concretely, we would have the following array:

• A = [1 3 6 6 9].

We would then iterate through A. Define S = sum(arr). Every time we reach index i such that A[i] == S/3, we would iterate from j = i+1 until we reach index j such that A[j] == (2/3)S. This corresponds to a "middle" chunk which sums up to S/3. To verify the last chunk sums up to S/3, we would compute A[n] - A[j]. If this number equals S/3, then we have found a valid 3-chunk.

Unfortunately the runtime for this approach is O(n^2). Given that n < 5*10^5, in the worst case we will perform (5*10^5)^2 = 25*10^10 instructions, which will take approximately 25 seconds. Clearly this is too long. Given the input range, we need to come up with at worst a O(nlog n) algorithm.