Skip to content

3432. Count Partitions with Even Sum Difference

Description

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

Solutions

Solution 1: Prefix Sum

Thinking

We count cuts whose left and right sums differ by an even number. The parity of the difference is determined by the two running sums, so the whole array need not be rescanned.

\(l-r\) is even iff \(l\) and \(r\) have the same parity. Since \(l-r=2l-\textit{total}\), we can just maintain \(l\) and \(r\) while moving the cut.

Shift each of the first \(n-1\) elements from \(r\) into \(l\) and count the cuts with \((l-r)\bmod 2=0\).

We use two variables \(l\) and \(r\) to represent the sum of the left subarray and the right subarray, respectively. Initially, \(l = 0\) and \(r = \sum_{i=0}^{n-1} \textit{nums}[i]\).

Next, we traverse the first \(n - 1\) elements. Each time, we add the current element to the left subarray and subtract it from the right subarray. Then, we check if \(l - r\) is even. If it is, we increment the answer by one.

Finally, we return the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countPartitions(nums []int) (ans int) {
    l, r := 0, 0
    for _, x := range nums {
        r += x
    }
    for _, x := range nums[:len(nums)-1] {
        l += x
        r -= x
        if (l-r)%2 == 0 {
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function countPartitions(nums: number[]): number {
    let l = 0;
    let r = nums.reduce((a, b) => a + b, 0);
    let ans = 0;
    for (const x of nums.slice(0, -1)) {
        l += x;
        r -= x;
        ans += (l - r) % 2 === 0 ? 1 : 0;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn count_partitions(nums: Vec<i32>) -> i32 {
        let mut l: i64 = 0;
        let mut r: i64 = nums.iter().map(|&x| x as i64).sum();
        let mut ans: i32 = 0;

        for &x in nums[..nums.len() - 1].iter() {
            l += x as i64;
            r -= x as i64;
            if (l - r) % 2 == 0 {
                ans += 1;
            }
        }

        ans
    }
}

Comments