# Count Partitions with Even Sum Difference
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-partitions-with-even-sum-difference)
Canonical: https://scaleengineer.com/dsa/problems/count-partitions-with-even-sum-difference
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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**.

**Example 1:**

**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:**

**Input:** nums = \[1,2,2\]

**Output:** 0

**Explanation:**

No partition results in an even sum difference.

**Example 3:**

**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`

# Approaches
## Brute Force Simulation
This approach directly follows the problem description. It iterates through every possible partition point, calculates the sum of the left and right subarrays for each partition from scratch, and checks if their difference is even.
**Time:** O(n^2), where n is the length of the array. The outer loop runs n-1 times. Inside the loop, we iterate through the array again to calculate the left and right sums, which takes O(n) time in total. This results in a quadratic time complexity. · **Space:** O(1), as we only use a few variables to store the sums and the count, requiring constant extra space.
**Pros:** Simple to understand and implement.; Directly translates the problem statement into code, making it a good first-pass solution.
**Cons:** Highly inefficient due to redundant calculations of subarray sums in each iteration.; The time complexity of O(n^2) might be too slow for larger input arrays, although it passes for the given constraints (n <= 100).
### Explanation
The most straightforward way to solve this problem is to simulate the process for every possible partition. A partition can be made at any index `i` from `0` to `n-2`, creating two non-empty subarrays.

For each such index `i`, we explicitly form the left subarray `[nums[0], ..., nums[i]]` and the right subarray `[nums[i+1], ..., nums[n-1]]`. We then iterate through both subarrays to compute their respective sums, `leftSum` and `rightSum`. Finally, we check if the difference `leftSum - rightSum` is an even number. If it is, we increment a counter. This process is repeated for all `n-1` possible partitions.

```java
class Solution {
    public int countPartitionsWithEvenDifference(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n - 1; i++) {
            // Calculate sum of the left subarray
            long leftSum = 0;
            for (int j = 0; j <= i; j++) {
                leftSum += nums[j];
            }

            // Calculate sum of the right subarray
            long rightSum = 0;
            for (int k = i + 1; k < n; k++) {
                rightSum += nums[k];
            }

            // Check if the difference is even
            if ((leftSum - rightSum) % 2 == 0) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through all possible partition indices `i` from `0` to `n-2`.
- For each `i`:
  - Create a nested loop to calculate the sum of the left subarray `nums[0...i]`, let's call it `leftSum`.
  - Create another nested loop to calculate the sum of the right subarray `nums[i+1...n-1]`, let's call it `rightSum`.
  - Calculate the difference `diff = leftSum - rightSum`.
  - If `diff` is even (i.e., `diff % 2 == 0`), increment the `count`.
- After the outer loop finishes, return `count`.

## Optimized Iteration with Prefix Sum
This approach improves upon the brute-force method by avoiding recalculating sums from scratch in each iteration. We first compute the total sum of the array. Then, as we iterate through the partition points, we can maintain a running sum for the left subarray and derive the right subarray's sum efficiently in constant time.
**Time:** O(n), where n is the length of the array. We have one pass to calculate the total sum (O(n)) and another pass to iterate through the partitions (O(n)). This results in a total time complexity of O(n) + O(n) = O(n). · **Space:** O(1), as we only use a few variables for the sums and the count.
**Pros:** Much more efficient than the brute-force approach with a linear time complexity.; Still relatively easy to understand and implement.
**Cons:** While efficient, it still performs more calculations than strictly necessary, as the result can be determined without iterating through all partitions.
### Explanation
The bottleneck in the brute-force approach is the repeated summation of subarrays. We can optimize this by pre-calculating the total sum of all elements in `nums`. Let `totalSum` be this sum.

For any partition at index `i`, if we know the sum of the left subarray (`leftSum`), the sum of the right subarray can be found in O(1) time as `rightSum = totalSum - leftSum`. We can iterate from `i = 0` to `n-2`, maintaining the `leftSum` as a running total. In each step, we add `nums[i]` to the current `leftSum` and then calculate the corresponding `rightSum` to check the parity of their difference.

```java
class Solution {
    public int countPartitionsWithEvenDifference(int[] nums) {
        int n = nums.length;
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int count = 0;
        long leftSum = 0;
        // Iterate through all possible partition points
        for (int i = 0; i < n - 1; i++) {
            leftSum += nums[i];
            long rightSum = totalSum - leftSum;
            if ((leftSum - rightSum) % 2 == 0) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- First, iterate through the entire array once to calculate the `totalSum`.
- Initialize a counter `count` to 0 and a `leftSum` to 0.
- Iterate with an index `i` from `0` to `n-2`.
- In each iteration:
  - Add `nums[i]` to `leftSum`.
  - Calculate `rightSum` using the formula `rightSum = totalSum - leftSum`.
  - Check if `(leftSum - rightSum) % 2 == 0`. If it is, increment `count`.
- Return `count`.

## Mathematical Insight with Parity
This is the most efficient approach, based on a key mathematical observation about the parity of the sum difference. It avoids iterating through partitions altogether and determines the answer by simply analyzing the parity of the total sum of the array.
**Time:** O(n), where n is the length of the array. We only need a single pass to calculate the total sum. This is the optimal time complexity as we must look at each element at least once. · **Space:** O(1), as we only need a single variable to store the running sum.
**Pros:** Most efficient solution in terms of both time and space.; Elegant and concise, solving the problem with a single pass and a simple check.; Avoids unnecessary iterations and calculations.
**Cons:** Requires a mathematical insight that might not be immediately obvious upon first reading the problem.
### Explanation
Let `S_left` be the sum of the left subarray and `S_right` be the sum of the right subarray. Let `TotalSum` be the sum of the entire array. We know that `S_left + S_right = TotalSum`.

The difference we are interested in is `Diff = S_left - S_right`.
We can express `S_right` in terms of `S_left` and `TotalSum`: `S_right = TotalSum - S_left`.

Substituting this into the difference equation gives: `Diff = S_left - (TotalSum - S_left) = 2 * S_left - TotalSum`.

Now, let's analyze the parity of this expression. The term `2 * S_left` is always an even number, regardless of the value or parity of `S_left`. Therefore, the parity of `Diff` depends solely on the parity of `TotalSum`.
- If `TotalSum` is **even**, `Diff = (even number) - (even number)`, which is always **even**.
- If `TotalSum` is **odd**, `Diff = (even number) - (odd number)`, which is always **odd**.

This crucial insight means that if the total sum of the array is even, *every* possible partition will result in an even difference. If the total sum is odd, *no* partition will. The number of possible partitions is `n-1` (for `i` from `0` to `n-2`).

```java
class Solution {
    public int countPartitionsWithEvenDifference(int[] nums) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (totalSum % 2 == 0) {
            // If total sum is even, any partition will have an even difference.
            // There are n-1 possible partitions.
            return nums.length - 1;
        } else {
            // If total sum is odd, no partition will have an even difference.
            return 0;
        }
    }
}
```
### Algorithm
- Calculate the `TotalSum` of all elements in the array `nums`.
- Check the parity of `TotalSum`.
- If `TotalSum` is even (`TotalSum % 2 == 0`), the difference will always be even. Return `n-1`, which is the total number of possible partitions.
- If `TotalSum` is odd, the difference will always be odd. Return `0`.

# Solutions
### Java

```java
class Solution {
public
  int countPartitions(int[] nums) {
    int l = 0, r = 0;
    for (int x : nums) {
      r += x;
    }
    int ans = 0;
    for (int i = 0; i < nums.length - 1; ++i) {
      l += nums[i];
      r -= nums[i];
      if ((l - r) % 2 == 0) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countPartitions(vector<int> &nums) {
    int l = 0, r = accumulate(nums.begin(), nums.end(), 0);
    int ans = 0;
    for (int i = 0; i < nums.size() - 1; ++i) {
      l += nums[i];
      r -= nums[i];
      if ((l - r) % 2 == 0) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPartitions(self, nums: List[int]) -> int: l, r = 0, sum(nums) ans = 0 for x in nums[: - 1]: l += x r -= x ans += (l - r) % 2 == 0 return ans

```