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}\mathit{\text{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 $\mathit{\text{nums}}$. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript

• 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