Counting Subarrays with Even Sum Using Prefix Sum Parity in C
C
Hard
28 views
Problem Description
Count subarrays whose sum is an even number - How do you provide the mathematical logic to count combinations by tracking the parity (odd/even) of the prefix sum?
Official Solution
#include <stdio.h>
int main() {
int arr[100], n;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter array elements:n");
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
int prefixSum = 0;
int evenCount = 1; // prefix sum 0 is even
int oddCount = 0;
for (int i = 0; i < n; i++) {
prefixSum += arr[i];
if (prefixSum % 2 == 0)
evenCount++;
else
oddCount++;
}
int totalEvenSubarrays = (evenCount * (evenCount - 1)) / 2 + (oddCount * (oddCount - 1)) / 2;
printf("Total subarrays with even sum = %dn", totalEvenSubarrays);
return 0;
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!