Count Splits with an Even Sum Difference
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
Given an integer array `nums` of length `n`, choose a split index `i` with `0 <= i < n - 1`. It divides the array into two nonempty contiguous parts:
- the left part contains indices `0` through `i`;
- the right part contains indices `i + 1` through `n - 1`.
Count the split indices for which the sum of the left part minus the sum of the right part is even. Return that count.
### C++ Interface
```cpp
class Solution {
public:
int countPartitions(vector<int>& nums) {
}
};
```
### Examples
**Example 1**
```text
Input: nums = [1,3,2,4]
Output: 3
```
The three splits have sum differences `1 - 9 = -8`, `4 - 6 = -2`, and `6 - 4 = 2`. All three differences are even.
**Example 2**
```text
Input: nums = [2,5,4]
Output: 0
```
The possible differences are `2 - 9 = -7` and `7 - 4 = 3`. Both are odd.
### Constraints
- `2 <= n == nums.length <= 100`.
- `1 <= nums[i] <= 100`.
### Clarifying Questions
- May either part be empty? No. There are exactly `n - 1` candidate split indices.
- Does a negative even difference qualify? Yes; `-8`, for example, is even.
- Are arbitrary subsets allowed? No. Each split separates one prefix from its remaining suffix.
### What a Strong Answer Covers
- The exact set of legal split positions and the nonempty requirement.
- Evenness of the difference, including negative differences.
- Correct counts for a two-element array and for arrays containing both odd and even values.
- A justification of the counting rule and its resource bounds.
### Follow-up Questions
- Would using the absolute difference change which splits qualify?
- If the required difference were divisible by three instead of two, what information would matter for an individual split?
```hint Relate the sums
For any split, the left and right sums add up to the same whole-array sum. Express their difference using that total and one of the two sums, then inspect its parity.
```
Overview: Count splits into nonempty contiguous left and right parts whose sum difference is even. Include negative differences and justify the count from the array total.