Today’s problem

3432. Count Partitions with Even Sum Difference

Intuition

In this question, we need to partition the array into two parts. And the difference between these two parts are even.

Now, both parts must have the same module to 2. That is, they are both even or both odd. So, the sum of the array needs to be even.

Now, if the sum of the array is even, then every partition must have the same module to 2. Otherwise, the sum of the array would be odd.

Therefore, the answer would be 0 when the sum of the array is odd, and $n-1$ when the sum of the array is even.

Approach

Return 0 when the sum of the array is odd, and $n-1$ when the sum of the array is even.

Complexity

• Time complexity:

$O(n)$, n is the length of the array.

• Space complexity:

$O(n)$, n is the length of the array.

Code

class Solution:
    def countPartitions(self, nums: List[int]) -> int:
        if sum(nums) % 2 == 1:
            return 0
        return len(nums) - 1