LeetCode 1524: Number of Sub-arrays With Odd Sum Solution

Master LeetCode problem 1524 (Number of Sub-arrays With Odd Sum), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1524. Number of Sub-arrays With Odd Sum

Medium

Array Math Dynamic Programming Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can iterate through the array and keep track of the cumulative sum at each index. At each index, we can determine the sum of subarrays ending at that index. If the sum is odd, we increment a counter. To calculate the number of subarrays with odd sum, we can consider the number of odd and even prefixes before the current index. The total number of subarrays ending at the current index with an odd sum is the product of the number of odd and even prefixes.

Algorithm

Initialize variables: oddCount = 0, evenCount = 1, sum = 0, result = 0.
Iterate through the array: a. Update sum by adding the current element. b. If sum is even, increment evenCount. c. If sum is odd, increment oddCount. d. Update result by adding oddCount * evenCount.
Return result % (10^9 + 7).

Time Complexity

The time complexity of this algorithm is O(n) where n is the number of elements in the input array.

Space Complexity

The space complexity is O(1) as we are using a constant amount of extra space.

Solution Code

class Solution {
    public int numOfSubarrays(int[] arr) {
        int oddCount = 0, evenCount = 1, sum = 0, result = 0;
        
        for (int num : arr) {
            sum += num;
            if (sum % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
            result += (oddCount * evenCount) % 1000000007;
        }
        
        return result % 1000000007;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1524 (Number of Sub-arrays With Odd Sum)?

This page provides optimized solutions for LeetCode problem 1524 (Number of Sub-arrays With Odd Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1524 (Number of Sub-arrays With Odd Sum)?

The time complexity for LeetCode 1524 (Number of Sub-arrays With Odd Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1524 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1524 in Java, C++, or Python.

Back to LeetCode Solutions