Scale Engineer

Count Partitions with Even Sum Difference

Easy
#3050Time: 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.
Patterns
MathPrefix Sum
Data structures
Array

Prompt

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

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 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.

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).

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem