This is documentation for my solution to 466C - Number of Ways. Credit for 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 chunks where each chunk is contiguous. Further, the sum of the elements in each chunk must be the same.
Naive Approach
My first approach to this problem was to pre-compute an array A
which is a running sum of arr
. Concretely, A[i] = sum(a[:i])
inclusive.