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.