Input: nums =[10,10,3,7,6]Output: 4Explanation:
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.
The difference between the left and right subarray sums is even if and only if the total sum and the left sum have the same parity. We can use prefix sums to efficiently check the parity at each partition.
classSolution {
public:int countPartitions(vector<int>& nums) {
int n = nums.size(), ans =0, total =0, pre =0;
for (int x : nums) total += x;
for (int i =0; i < n -1; ++i) {
pre += nums[i];
if ((pre %2) == (total %2)) ans++;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
classSolution {
publicintcountPartitions(int[] nums) {
int n = nums.length, ans = 0, total = 0, pre = 0;
for (int x : nums) total += x;
for (int i = 0; i < n - 1; i++) {
pre += nums[i];
if ((pre % 2) == (total % 2)) ans++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
defcountPartitions(self, nums: list[int]) -> int:
n = len(nums)
total = sum(nums)
pre =0 ans =0for i in range(n-1):
pre += nums[i]
if (pre %2) == (total %2):
ans +=1return ans