Count Partitions with Even Sum Difference

This approach directly follows the problem description. It iterates through every possible partition point, calculates the sum of the left and right subarrays for each partition from scratch, and checks if their difference is even.

• Initialize a counter count to 0.
• Iterate through all possible partition indices i from 0 to n-2.
• For each i:
  • Create a nested loop to calculate the sum of the left subarray nums[0...i], let's call it leftSum.
  • Create another nested loop to calculate the sum of the right subarray nums[i+1...n-1], let's call it rightSum.
  • Calculate the difference diff = leftSum - rightSum.
  • If diff is even (i.e., diff % 2 == 0), increment the count.
• After the outer loop finishes, return count.

The most straightforward way to solve this problem is to simulate the process for every possible partition. A partition can be made at any index i from 0 to n-2, creating two non-empty subarrays.

For each such index i, we explicitly form the left subarray [nums[0], ..., nums[i]] and the right subarray [nums[i+1], ..., nums[n-1]]. We then iterate through both subarrays to compute their respective sums, leftSum and rightSum. Finally, we check if the difference leftSum - rightSum is an even number. If it is, we increment a counter. This process is repeated for all n-1 possible partitions.

class Solution {
    public int countPartitionsWithEvenDifference(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n - 1; i++) {
            // Calculate sum of the left subarray
            long leftSum = 0;
            for (int j = 0; j <= i; j++) {
                leftSum += nums[j];
            }

            // Calculate sum of the right subarray
            long rightSum = 0;
            for (int k = i + 1; k < n; k++) {
                rightSum += nums[k];
            }

            // Check if the difference is even
            if ((leftSum - rightSum) % 2 == 0) {
                count++;
            }
        }
        return count;
    }
}