Welcome to Subscribe On Youtube

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

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

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

All Problems

All Solutions