Count Partitions with Even Sum Difference
EasyPrompt
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 of10 - 26 = -16, which is even.[10, 10],[3, 7, 6]with a sum difference of20 - 16 = 4, which is even.[10, 10, 3],[7, 6]with a sum difference of23 - 13 = 10, which is even.[10, 10, 3, 7],[6]with a sum difference of30 - 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 <= 1001 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a counter
countto 0. - Iterate through all possible partition indices
ifrom0ton-2. - For each
i:- Create a nested loop to calculate the sum of the left subarray
nums[0...i], let's call itleftSum. - Create another nested loop to calculate the sum of the right subarray
nums[i+1...n-1], let's call itrightSum. - Calculate the difference
diff = leftSum - rightSum. - If
diffis even (i.e.,diff % 2 == 0), increment thecount.
- Create a nested loop to calculate the sum of the left subarray
- After the outer loop finishes, return
count.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- First, iterate through the entire array once to calculate the
totalSum. - Initialize a counter
countto 0 and aleftSumto 0. - Iterate with an index
ifrom0ton-2. - In each iteration:
- Add
nums[i]toleftSum. - Calculate
rightSumusing the formularightSum = totalSum - leftSum. - Check if
(leftSum - rightSum) % 2 == 0. If it is, incrementcount.
- Add
- Return
count.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Calculate the
TotalSumof all elements in the arraynums. - Check the parity of
TotalSum. - If
TotalSumis even (TotalSum % 2 == 0), the difference will always be even. Returnn-1, which is the total number of possible partitions. - If
TotalSumis odd, the difference will always be odd. Return0.
Walkthrough
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
TotalSumis even,Diff = (even number) - (even number), which is always even. - If
TotalSumis 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).
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; } }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.