We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Partitions with Even Sum Difference

Number: 3704

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums of length n, a partition is defined as an index i (0 <= i < n - 1) that splits the array into two non-empty subarrays, with the left subarray consisting of nums[0..i] and the right subarray consisting of nums[i+1..n-1]. The task is to return the number of partitions such that the difference between the sum of the left subarray and the sum of the right subarray is even.

Key Insights

  • The difference between the sum of the left and right subarrays can be written as 2 * (sum of left) - (total sum).
  • Notice that 2 * (sum of left) is always even.
  • Thus, the parity of the difference depends solely on the parity of the total sum.
  • If the total sum is even, then for any partition the difference will be even.
  • If the total sum is odd, the difference will always be odd for every partition.
  • Therefore, if the total sum is even the answer is the total number of valid partitions (which is n - 1), otherwise the answer is 0.

Space and Time Complexity

Time Complexity: O(n) – to compute the total sum of the array. Space Complexity: O(1) – only constant extra space is used.

Solution

The solution first calculates the total sum of the array. Because the partitioning difference is formulated as 2 * (prefix sum) - (total sum) and 2 * (prefix sum) is always even, the difference is even if and only if the total sum is even. If the sum is even, every possible partition (there are n - 1 partitions) is valid. Otherwise, if the total sum is odd, no partition yields an even difference.

Code Solutions

# Python solution with line-by-line comments

def countEvenSumDifferencePartitions(nums):
    # Calculate the total sum of the array
    total_sum = sum(nums)
    # If the total sum is odd, no partition will yield an even difference.
    if total_sum % 2 != 0:
        return 0
    # Otherwise, every partition produces an even difference.
    # There are exactly (n - 1) valid partitions for an array of length n.
    return len(nums) - 1

# Example usage:
# nums = [10,10,3,7,6]
# print(countEvenSumDifferencePartitions(nums))  # Output: 4
← Back to All Questions