CODEWITHSUNDEEP
c++algorithm
user8305079
user8305079

Reputation:

Reasoning behind calculating the number of sub-arrays with odd sum

I am solving a question on LeetCode.com:

Given an array of integers arr. Return the number of sub-arrays with odd sum. As the answer may grow large, the answer must be computed modulo 10^9 + 7.
For arr = [1,3,5], the output is 4.

One of the highly upvoted solutions is like this:

int numOfSubarrays(vector<int>& arr) {
    int odd = 0, even = 0, sum = 0;
    for (int n : arr) {
        if (n % 2) {
            swap(odd, even);
            ++odd;
        }
        else
            ++even;
        sum = (sum + odd) % 1000000007;
    }
    return sum;
}

The author says, if we know the number of even and odd subarrays that end at the previous element, we can figure out how many even and odd subarrays we have for element n:

a. If n is even, we increase the number of even subarrays; the number of odd subarrays does not change.
b. If n is odd, the number of odd subarrays is the previous number of even subarrays + 1. The number of even subarrays is the previous number of odd subarrays.

I 'understand' the 'workflow', but not the logic or the intuition behind it. Specifically, I have the following questions:

a. What is an intuitive explanation of the steps mentioned by the author above?
b. How does it guarantee that all the sub-arrays have been accounted for? For e.g., in the above example, how is sub-array [3,5] account for, in the logic?

Thanks!

Upvotes: 0

Views: 601

Answers (1)

eesiraed
eesiraed

Reputation: 4654

First of all, we need to understand some basic properties of parity. If a is even, then the parity of a + b is the same as the parity of b. If a is odd, then the parity of a + b is the opposite of the parity of b.

In the code that you've posted, odd is the number of subarrays ending at the current element which have odd sums. even is the number of subarrays ending at the current element which have even sums. sum is the number of subarrays ending at or before the current element which have odd sums.

If the current element is even, then appending this element to any subarray preserves its sum parity. Therefore, the number of subarrays ending at the current element with an even sum is the same as the number of subarrays ending at a previous element with an even sum plus one, because every subarray ending at the current position is either a subarray ending at the previous position with the current element appended, or is a subarray of length one containing the current element. The number of subarrays ending at the current element with an odd sum is the same as the number of subarrays ending at the previous element with an odd sum, because every subarray ending at the current position with an odd sum is the same as a subarray ending at the previous element with the current element appended. We don't have to count the subarray of length one containing the current element here because that has an even sum.

If the current element is odd, then adding it to any subarray flips its parity. Therefore, we swap odd and even and increment even to count the subarray of length one containing the current element.

At every step we add the number of subarrays ending at the current position with an odd sum to sum, so at the end sum will contain the number of subarrays with odd sum ending at any position.

Upvotes: 1

Related Questions