Python 1524.py
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
result = 0
total = 0
odd = 0
even = 1 # pretend to prepend a zero
for a in arr:
total += a
if total & 1:
result += even
odd += 1
else:
result += odd
even += 1
return result % 1_000_000_007
Difficulty
and has an acceptance rate of about 56% (300k+ submissions).
Typical patterns to solve this problem:
- Array
- Dynamic Programming
- Math
- Prefix Sum
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation computes the number of sub-arrays whose sum is odd. It processes the input list in a single forward pass, maintaining cumulative information that enables constant-time updates for each element. The final answer is returned modulo 1 000 000 007, which keeps the result within the range of a 32-bit signed integer even for very large inputs.
Initialization
At the start, four integer variables are created:
result = 0
total = 0
odd = 0
even = 1 # pretend to prepend a zero
result accumulates the count of qualifying sub-arrays. total holds the running prefix sum of the processed elements. odd and even count how many prefix sums encountered so far have odd and even parity, respectively. The initial even = 1 represents the empty prefix (sum = 0), which is even and serves as a baseline for sub-arrays that start at index 0.
Main Loop
The core of the algorithm iterates over each element a in the input list arr:
for a in arr:
total += a
if total & 1:
result += even
odd += 1
else:
result += odd
even += 1
During each iteration the running sum total is updated. The expression total & 1 checks the least-significant bit, determining whether the current prefix sum is odd. If the prefix sum is odd, every previously seen even-parity prefix can be paired with the current position to form an odd-sum sub-array; therefore result is increased by even. The counter odd is then incremented because the current prefix itself is odd. Conversely, when the prefix sum is even, the algorithm adds odd to result and increments even.
This parity-based counting eliminates the need to examine each possible sub-array explicitly. By tracking only the counts of odd and even prefixes, the algorithm implicitly accounts for all sub-arrays ending at the current index.
Edge Cases Handled
When the input list is empty, the loop body never executes. The counters remain at their initial values (result = 0, even = 1), and the function returns 0, correctly indicating that there are no sub-arrays.
If all elements are zero, each prefix sum stays even. The else branch runs on every iteration, adding the current odd count (which stays 0) to result. Consequently, result remains 0, reflecting that no sub-array has an odd sum.
Large integer values in arr are safely accumulated in total because Python integers have arbitrary precision. The final modulo operation ensures that the returned value fits within the required range, regardless of how large the intermediate result becomes.
Result Computation
After processing the entire array, the function applies the modulus:
return result % 1_000_000_007
Performing the modulo only once, at the end, reduces the overhead of repeated modular reductions inside the loop. This design choice leverages the fact that Python’s integer arithmetic can handle very large numbers without overflow, allowing the algorithm to keep the inner loop tight and fast.
Performance Optimizations
The algorithm achieves high efficiency by:
- Traversing the input exactly once, avoiding nested loops or repeated scans.
- Maintaining only four scalar variables, which results in constant auxiliary memory usage.
- Using a bitwise AND (
total & 1) to test parity, which is faster than arithmetic modulo operations. - Deferring the modulo operation until after the loop, minimizing the number of expensive division operations.
These choices collectively produce a solution that scales linearly with the length of arr while keeping the runtime overhead minimal.
ELI5 - Simplified Explanation
Imagine a long train track made of many colorful blocks. Some blocks represent odd numbers and some represent even numbers. The goal is to see how many different sections of this track add up to an odd number.
Think of walking along the track while carrying a basket. Every time a new block is added to the total, it changes whether the sum is odd or even.
There is a little counter kept for how many times the total sum has been even and how many times it has been odd so far. To make sure the math works perfectly from the very beginning, the count for even sums starts at one because a starting total of zero is an even number.
As each block from the track is picked up, it is added to the running total. If the new total is odd, it means that by pairing this current spot with every previous spot that had an even total, a new odd section is created. All those previous even spots are added to the running score, and then the odd count goes up by one.
If the new total is even instead, it means that pairing this current spot with every previous spot that had an odd total creates an odd section. All those previous odd spots are added to the running score, and the even count goes up by one.
This process repeats for every single block on the track until the very end. The final number tells exactly how many odd sections exist.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | |||||||||
| leetcode.ca | C++ | Python | Java | Go | Rust | TS | ||||
| Progiez | C++ | Python | Java | |||||||
| github | black-shadows | C++ | ||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| FelixFan1122 | Java | |||||||||
| fsq | C++ | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| Shamik07 | Dart | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| wisdompeak | C++ | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++ | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| Progiez | C++, Java, Python | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| FelixFan1122 | Java | |||||||||
| fsq | C++ | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| Shamik07 | Dart | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| wisdompeak | C++ |
Videos
Solved On The Same Day
- problem 1319: Number of Operations to Make Network Connected
- problem 1465: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
- problem 1477: Find Two Non-overlapping Sub-arrays Each With Target Sum
- problem 1482: Minimum Number of Days to Make m Bouquets
- problem 1488: Avoid Flood in The City
- problem 1546: Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
- problem 1562: Find Latest Group of Size M
- problem 1567: Maximum Length of Subarray With Positive Product
- problem 1320: Minimum Distance to Type a Word Using Two Fingers
- problem 1697: Checking Existence of Edge Length Limited Paths
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality