Partition Array Into Three Parts With Equal Sum

Problem

Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Constraints

• 3 <= arr.length <= 5 * 104
• -104 <= arr[i] <= 104

Solution

The problem Partition Array Into Three Parts With Equal Sum can be solved by calculating the total sum of the given array. If the sum is divisible by 3, then we can check if there are 3 partial sums in the array that are all equal. If there are at least 2 partial sums that satisfies partial sum = total sum / 3, then it is obvious that the part that is left will have the same sum as the others since total sum - 2 * partial sum = 3 * partial sum - 2 * partial sum = partial sum.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool canThreePartsEqualSum(vector<int> &arr)
    {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        if (sum % 3)
            return false;

        int part = 0;
        int count = 0;

        for (int num : arr)
        {
            part += num;
            if (part * 3 == sum)
            {
                part = 0;
                count += 1;
            }
        }

        return count >= 3;
    }
};