Problem 1524

Abstract / Summary

Count how many subarrays have an odd total sum in a given list of integers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
18 lines | 435 bytes | submitted May 3, 2024 | GitHub   6% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 56% (300k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Dynamic Programming
  • Math
  • Prefix Sum
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.19 | σ = 0.94

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
27 links | 17 authors | 9 languages

Videos

7 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

11 solutions   May 3, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • 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