1524. Number of Sub-arrays With Odd Sum

MediumArrayMathDynamic ProgrammingPrefix Sum
Leetcode Link

Problem Description

The task is to count how many subarrays (continuous parts of the array) of a given array of integers have a sum that is odd. It's important to note that the array consists of integers which may be positive, negative, or zero.

Subarrays are defined as slices of the original array that maintain the order of elements. For example, if the array is [1, 2, 3], then [1, 2] and [2, 3] are subarrays, but [1, 3] is not a subarray because it doesn't preserve the order of elements.

Since the number of possible subarrays for even a moderate-sized array is quite large, and therefore the result could be a very large number, the problem asks to return the count of such subarrays modulo 10^9 + 7. This is a common requirement for such problems to avoid issues with large number handling.

In short, we need to find the total count of subarrays with odd sums and then report this count modulo 10^9 + 7.

Intuition

When we want to solve a problem related to subarrays and their sums, a common approach is to think in terms of prefix sums. A prefix sum is the cumulative sum of elements from the start of the array up to a given point. It allows us to quickly calculate the sum of any subarray by subtracting the prefix sum up to the start of the subarray from the prefix sum up to the end of the subarray.

To solve this problem, we initialize a count array cnt of size 2, where cnt[0] keeps track of the number of even prefix sums encountered so far and cnt[1] keeps track of the odd ones. Initially, cnt is set to [1, 0], meaning we have one even prefix sum (which is the zero-sum before we start the sum, equivalent to an empty subarray), and no odd sums.

We iterate through the input array arr and update our current running sum s. At each element, we use the property that odd - even = odd and even - odd = odd to determine if the current prefix sum would lead to a subarray with an odd sum, given previous prefix sums.

The expression (s & 1) gives us 1 if s (the current prefix sum) is odd, and 0 if it's even. We use this to update our cnt array to count the occurrences of even and odd prefix sums.

For each new element x added to our running sum s, we look at "s & 1 ^ 1", which essentially flips the parity; if s is even, we look at odd counts (cnt[1]), if s is odd, we look at even counts (cnt[0]). We add this to our answer ans, which keeps track of the total count of subarrays with odd sum encounters so far. We then update the cnt array to reflect the new counts after considering the current element.

Lastly, we return ans, the total count, modulo 10^9 + 7 to keep the number within bounds per the problem statement's requirements.

This solution takes O(n) time, where n is the number of elements in arr, and O(1) extra space, making it efficient for even large arrays.

Learn more about Math, Dynamic Programming and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Solution Approach

The solution uses a single pass through the array and leverages bitwise operations and modular arithmetic to maintain and calculate the count of subarrays with odd sums efficiently.

Here's a step-by-step walkthrough:

  1. Initialize mod to 10^9 + 7. This will be used to perform modular arithmetic to ensure that the result remains within integer limits.

  2. Declare a list cnt with [1, 0] which represents the count of prefix sums that are even and odd. cnt[0] is initially 1 because a prefix sum of 0 (before processing any elements) is even.

  3. Initialize ans (the variable to store the final count of subarrays with odd sums) to 0 and s (the running prefix sum) to 0.

  4. Iterate through each element x in the array arr.

    a. Add x to the running prefix sum s.

    b. Calculate (s & 1) to get the parity of the prefix sum s. s & 1 will be 1 for odd and 0 for even. This is a standard way to check for even or odd numbers using bitwise AND operation.

    c. Calculate s & 1 ^ 1 to flip the current parity. We use bitwise XOR here to flip 0 to 1 and 1 to 0. This is because if the current prefix sum s is even, we are interested in the count of previously seen odd prefix sums to form an odd subarray and vice versa.

    d. Update ans by adding the count of prefix sums of the opposite parity (cnt[s & 1 ^ 1]). It's important to note that if we have an odd prefix sum now and an even prefix sum previously, the subarray between the two will have an odd sum.

    e. Apply the modulo operation to ensure that ans does not overflow integer limits.

    f. Increment the count of the appropriate parity in cnt by 1 (cnt[s & 1]).

  5. After the loop, return ans, which now contains the moduloed count of subarrays with odd sums.

The code uses a for loop that iterates through every element in the array, maintaining a running prefix sum which allows us to determine, at each step, how many subarrays ended at this element have an odd sum. The use of the prefix sum pattern is crucial here because it helps in determining the sum of subarrays in constant time without the need to recalculate sums for each potential subarray.

In terms of data structures, the solution keeps a small array cnt to count even and odd sums, rather than a prefix sum array, which would normally be used in prefix sum problems. This is an optimization that takes advantage of the problem's specifics (only the parity of the sums is relevant).

The code is concise and efficient, running in O(n) time complexity with constant space usage, which is optimal for this problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's illustrate the solution approach using a small example array: arr = [1, 2, 3, 4]. We're tasked with finding the count of subarrays that have an odd sum.

  1. Initialize mod to 10^9 + 7 for modular arithmetic.

  2. cnt starts as [1, 0], indicating one even prefix sum (0 from no elements) and no odd prefix sums.

  3. ans is set to 0 and s (the running prefix sum) is also 0.

  4. Start iterating through each element x in arr.

    a. For x = 1: s becomes 1.

    b. (s & 1) gives us 1, indicating the current prefix sum is odd.

    c. s & 1 ^ 1 yields 0, so we look at the even counts from cnt.

    d. ans is updated with cnt[0], which is 1, because adding an odd number (1) to any even prefix sums would result in an odd sum subarray (in this case, the subarray is just [1]).

    e. Apply a modulo to ans if needed.

    f. Increment cnt[1] since we now have an odd prefix sum (1).

    After the first iteration: s = 1, cnt = [1, 1], ans = 1.

  5. For x = 2:

    a. s becomes 3.

    b. (s & 1) gives us 1, so the current prefix sum is odd.

    c. s & 1 ^ 1 yields 0, so we look at the even counts from cnt.

    d. ans is updated with cnt[0], which is 1, because an even number added to an odd prefix sum keeps the sum odd ([1, 2] is the new odd subarray).

    e. Apply a modulo to ans.

    f. Increment cnt[1] since our running sum is still odd.

    After the second iteration: s = 3, cnt = [1, 2], ans = 2.

  6. For x = 3:

    a. s becomes 6.

    b. (s & 1) gives us 0, so the current prefix sum is even.

    c. s & 1 ^ 1 yields 1, now we look at the odd counts from cnt.

    d. ans is updated with cnt[1], which is 2. The addition of an odd number (3) to the previous odd prefix sums creates new odd sum subarrays ([1, 2, 3] and [3]).

    e. Apply a modulo to ans.

    f. Increment cnt[0] because s is now even.

    After the third iteration: s = 6, cnt = [2, 2], ans = 4.

  7. For x = 4:

    a. s becomes 10.

    b. (s & 1) gives us 0, meaning an even prefix sum.

    c. s & 1 ^ 1 flips to 1, looking at odd counts in cnt.

    d. ans is updated with cnt[1], which is 2. Even prefix sums followed by an even number do not change the parity ([2, 3, 4] and [4] are the new subarrays).

    e. Apply a modulo to ans.

    f. Increment cnt[0] as s remains even.

    Final state: s = 10, cnt = [3, 2], ans = 6.

  8. Return ans, which is 6. This means there are 6 subarrays with an odd sum in arr = [1, 2, 3, 4]. The result is given modulo 10^9 + 7.

The solution approach effectively identifies all possible subarrays with odd sums by keeping track of prefix sums and their parity, using a simple count array and adding the counts of prefix sums with the opposite parity when encountering a new element. Hence, we achieve an O(n) time complexity solution with constant space utilization.

Solution Implementation

1class Solution:
2    def numOfSubarrays(self, arr: List[int]) -> int:
3        # Define a large number for modulo operation to prevent integer overflow
4        mod = 10**9 + 7
5      
6        # Initialize the count of subarrays with even and odd sum
7        count = [1, 0]  # Even sums are initialized to 1 due to the virtual prefix sum of 0 at the start
8      
9        # Initialize answer and prefix sum variables
10        answer = 0
11        prefix_sum = 0
12      
13        # Iterate over the array elements
14        for num in arr:
15            # Update the prefix sum
16            prefix_sum += num
17          
18            # Increment the answer by the number of subarrays encountered so far
19            # that when added to the current element yields an even sum
20            answer = (answer + count[prefix_sum % 2 ^ 1]) % mod
21          
22            # Update the count of subarrays with current sum parity
23            count[prefix_sum % 2] += 1
24          
25        # Return the final answer
26        return answer
27
1class Solution {
2
3    // Method to calculate the number of subarrays with odd sum
4    public int numOfSubarrays(int[] arr) {
5        // Initialize the modulus value as per the problem statement
6        final int MOD = 1000000007;
7      
8        // Counter array to track even and odd sums, where index 0 is for even and index 1 is for odd
9        int[] count = {1, 0};
10      
11        // Variable to store the final answer
12        int answer = 0;
13      
14        // Variable to store the current sum
15        int sum = 0;
16      
17        // Iterate through each element in the array
18        for (int num : arr) {
19            // Add the current element's value to the cumulative sum
20            sum += num;
21          
22            // If the cumulative sum is odd, add the count of previous even sums to the answer.
23            // If the cumulative sum is even, add the count of previous odd sums to the answer.
24            // Then, take the modulo to handle large numbers
25            answer = (answer + count[1 - (sum & 1)]) % MOD;
26          
27            // Increment the count of current parity (even/odd) of sum
28            ++count[sum & 1];
29        }
30      
31        // Return the final answer
32        return answer;
33    }
34}
35
1class Solution {
2public:
3    int numOfSubarrays(vector<int>& arr) {
4        const int MOD = 1000000007; // The modulus value for avoiding integer overflow
5        int count[2] = {1, 0}; // Initialize count array to keep track of even (count[0]) and odd (count[1]) sums
6        int answer = 0; // This will store the final result, the number of subarrays with an odd sum
7        int sum = 0; // This variable will store the cumulative sum of the elements
8      
9        // Iterate over each element in the input array
10        for (int number : arr) {
11            sum += number; // Add the current number to the cumulative sum
12            // Increment the answer by the count of the opposite parity (even if sum is odd, odd if sum is even)
13            // This is because an odd sum - even sum = odd
14            answer = (answer + count[sum % 2 ^ 1]) % MOD;
15            // Increment the count of the current sum's parity (1 for odd, 0 for even)
16            ++count[sum % 2];
17        }
18      
19        return answer; // Return the total count of subarrays with an odd sum
20    }
21};
22
1function numOfSubarrays(arr: number[]): number {
2    let answer = 0;                  // Initializes the answer to 0.
3    let cumulativeSum = 0;           // Tracks the cumulative sum of the elements.
4    const count: number[] = [1, 0];  // count[0] represents count of even cumulative sums, count[1] represents count of odd cumulative sums.
5    const MOD = 1e9 + 7;             // Define the modulo value for the answer.
6
7    // Iterate through the given array.
8    for (const element of arr) {
9        cumulativeSum += element;    // Update the cumulative sum with the current element.
10
11        // Increment the answer with the amount of even cumulative sums if the current cumulative sum is odd
12        // or the amount of odd cumulative sums if the current cumulative sum is even, then take modulo.
13        answer = (answer + count[(cumulativeSum & 1) ^ 1]) % MOD;
14
15        // Increment the count of even/odd cumulative sums as appropriate.
16        count[cumulativeSum & 1]++;
17    }
18
19    return answer;                   // Return the final answer.
20}
21
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following array represent a max heap?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the input array arr. This is because there is a single for-loop that iterates through the array once, and the operations within the loop (calculating the sum s, updating ans, and managing cnt array) have constant time complexity.

Space Complexity

The space complexity of the code is O(1). The additional space used by the algorithm is limited to a few variables (mod, cnt, ans, s) and does not depend on the size of the input array. The cnt array is of fixed size 2, which stores the count of cumulative sums that are even and odd.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ