Problem

You are given an integer array nums of length n.

A partition is defined as an index i where 0 <= i < n - 1, splitting the array into two non-empty subarrays such that:

  • Left subarray contains indices [0, i].
  • Right subarray contains indices [i + 1, n - 1].

Return the number of partitions where the difference between the sum of the left and right subarrays is even.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: nums = [10,10,3,7,6]
Output: 4
Explanation:
The 4 partitions are:
* `[10]`, `[10, 3, 7, 6]` with a sum difference of `10 - 26 = -16`, which is even.
* `[10, 10]`, `[3, 7, 6]` with a sum difference of `20 - 16 = 4`, which is even.
* `[10, 10, 3]`, `[7, 6]` with a sum difference of `23 - 13 = 10`, which is even.
* `[10, 10, 3, 7]`, `[6]` with a sum difference of `30 - 6 = 24`, which is even.

Example 2

1
2
3
4

Input: nums = [1,2,2]
Output: 0
Explanation:
No partition results in an even sum difference.

Example 3

1
2
3
4

Input: nums = [2,4,6,8]
Output: 3
Explanation:
All partitions result in an even sum difference.

Constraints

  • 2 <= n == nums.length <= 100
  • 1 <= nums[i] <= 100

Solution

Method 1 – Prefix Sum and Parity

Intuition

The difference between the left and right subarray sums is even if and only if the total sum and the left sum have the same parity. We can use prefix sums to efficiently check the parity at each partition.

Approach

  1. Compute the total sum of the array.
  2. Iterate through the array, maintaining the prefix sum up to index i.
  3. For each partition (i from 0 to n-2):
    1. If (2 * prefix_sum[i] - total_sum) is even, increment the answer.
    2. This is equivalent to checking if prefix_sum[i] and total_sum have the same parity.
  4. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int countPartitions(vector<int>& nums) {
        int n = nums.size(), ans = 0, total = 0, pre = 0;
        for (int x : nums) total += x;
        for (int i = 0; i < n - 1; ++i) {
            pre += nums[i];
            if ((pre % 2) == (total % 2)) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int countPartitions(int[] nums) {
        int n = nums.length, ans = 0, total = 0, pre = 0;
        for (int x : nums) total += x;
        for (int i = 0; i < n - 1; i++) {
            pre += nums[i];
            if ((pre % 2) == (total % 2)) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def countPartitions(self, nums: list[int]) -> int:
        n = len(nums)
        total = sum(nums)
        pre = 0
        ans = 0
        for i in range(n-1):
            pre += nums[i]
            if (pre % 2) == (total % 2):
                ans += 1
        return ans

Complexity

  • ⏰ Time complexity: O(n), since we scan the array once for prefix sums.
  • 🧺 Space complexity: O(1), only a few variables are used.