3432. Count Partitions with Even Sum Difference

[mah-shamim]

Topics: Array, Math, Prefix Sum, Weekly Contest 434

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

Hint:

1. If the parity of the sum is even, the partition is valid; otherwise, there is no partition.

[mah-shamim]

We notice there's a critical flaw in the reasoning. Let me provide a corrected approach:

Approach:

1. Compute the total sum of the array
2. Track the left sum as we iterate through possible partition points
3. For each partition, calculate the right sum as total sum minus left sum
4. Check if the absolute difference between left and right sums is even
5. Count valid partitions

Let's implement this solution in PHP: 3432. Count Partitions with Even Sum Difference

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function countPartitions($nums) {
    $totalSum = array_sum($nums);
    $n = count($nums);

    // If total sum is even, every partition is valid
    if ($totalSum % 2 == 0) {
        return $n - 1;
    }

    // If total sum is odd, no partition is valid
    return 0;
}

// Test cases
echo countPartitions([10,10,3,7,6]) . "\n";     // Output: 4
echo countPartitions([1,2,2]) . "\n";           // Output: 0
echo countPartitions([2,4,6,8]) . "\n";         // Output: 3
?>

Explanation:

1. The problem asks for partitions where the difference between left and right sums is even
2. We need to consider all possible split points from index 0 to n-2
3. For each split point i:
   • Left sum = sum of elements from index 0 to i
   • Right sum = total sum - left sum
   • Difference = left sum - right sum (or absolute value)
   • Check if difference is even
4. Count all such partitions

[topugit]

Thanks for solving the problem of "Count Partitions with Even Sum Difference"

[mah-shamim]

Thanks