Leetcode 1523. Count Odd Numbers in an Interval Range

Let's understand what we're being asked to do. We have an inclusive interval [low, high] and need to count how many odd integers exist within it.

For example, given low = 3 and high = 7, the integers in this range are 3, 4, 5, 6, 7. The odd ones are 3, 5, 7, so we return 3.

Let's trace another example: low = 8 and high = 10 gives us 8, 9, 10. Only 9 is odd, so we return 1.

Important constraint: The bounds can be as large as 10^9, which means we cannot enumerate all integers in the range. If low = 1 and high = 1000000000, iterating through a billion numbers would be far too slow!

Edge cases to consider: What if both low and high are odd? What if both are even? What if low equals high? What if the range contains only one number?

The naive approach would be to iterate through every integer from low to high, checking each one to see if it's odd (using modulo operator num % 2 == 1), and incrementing a counter for each odd number found. While this is simple to understand and implement, it requires iterating through potentially billions of numbers, making it impractical for large ranges. This approach would work for small ranges but fails the constraint of handling bounds up to 10^9.

def count_odds(low, high):
    """
    Brute force: Iterate through every integer from low to high,
    checking each one to see if it's odd using modulo operator.
    This is inefficient for large ranges (up to 10^9).
    """
    # Initialize counter for odd numbers
    count = 0
    
    # Iterate through every integer in the range
    for num in range(low, high + 1):
        # Check if current number is odd
        if num % 2 == 1:
            # Increment counter if odd
            count += 1
    
    # Return total count of odd numbers
    return count

Odd numbers follow a regular pattern: they appear at every other position in the number line. In any consecutive sequence, roughly half the numbers are odd and half are even.

The key insight is that we don't need to check each number individually - we can use the structure of the range itself to calculate the count directly.

By recognizing the alternating pattern of odd/even numbers, we can transform this from a counting problem (which would require iteration) into a pure arithmetic calculation.

This makes the solution work in constant time O(1), regardless of whether the range contains 10 numbers or 1 billion numbers!

Think about how odd numbers are distributed on a number line. Between any two numbers, the count of odds depends on:

1. The total count of numbers in the range
2. Whether the endpoints are odd or even

For example, [1, 2, 3, 4, 5] has 5 numbers total. Since we start with odd 1, the pattern is odd-even-odd-even-odd, giving us 3 odds. But [2, 3, 4, 5, 6] also has 5 numbers, yet starts with even 2, so the pattern is even-odd-even-odd-even, giving us only 2 odds.

The formula involves the range size and whether we're starting/ending on odd or even boundaries.

The optimal approach uses pure arithmetic to calculate the count in constant time. The key formula is: (high - low) / 2 + 1 if both endpoints have the same parity (both odd or both even), otherwise (high - low + 1) / 2. This works because odd numbers alternate with even numbers, so in any range, approximately half are odd. The exact count depends on whether the range starts and ends on odd or even boundaries. By checking the parity of low and high using modulo operations, we can determine the precise count without any iteration.

def count_odds(low, high):
    """
    Count odd integers in range [low, high] using arithmetic.
    Time: O(1), Space: O(1)
    """
    # Check if both endpoints have same parity
    low_is_odd = low % 2 == 1
    high_is_odd = high % 2 == 1
    
    # Calculate count based on parity
    if low_is_odd and high_is_odd:
        # Both odd: (high - low) / 2 + 1
        count = (high - low) // 2 + 1
    elif low_is_odd or high_is_odd:
        # One odd: (high - low + 1) / 2
        count = (high - low + 1) // 2
    else:
        # Both even: (high - low) / 2
        count = (high - low) // 2
    
    return count

• Arithmetic counting over iteration: When asked to count elements in a range with a predictable pattern (odd/even numbers, multiples), use mathematical formulas instead of loops - this transforms O(n) enumeration into O(1) calculation, essential when bounds reach 10^9.
• Inclusive range formula: For odd numbers in [low, high], use `(high - low) / 2 + 1` when both have same parity, or `(high - low + 1) / 2` as the universal formula - the key insight is that integer division naturally handles both even and odd boundaries without complex conditionals.
• Parity-based problem recognition: Whenever a problem involves counting alternating patterns (odd/even, every nth element) in a range, immediately consider closed-form arithmetic solutions - these problems are disguised math exercises, not iteration challenges.
• Off-by-one in inclusive ranges: The most common mistake is forgetting the range is inclusive on both ends - for [3, 7], students often calculate 2 odds instead of 3 by missing that both boundaries count. Always add 1 to account for inclusive endpoints in your formula.
• Boundary condition testing: Test your formula with small manual cases like [1,1] (answer: 1), [1,2] (answer: 1), [2,2] (answer: 0), and [1,5] (answer: 3) - if your arithmetic works for these edge cases, it scales to 10^9 without modification.
• Range query optimization pattern: This technique extends to any range aggregation problem where you can derive the answer from boundary values alone - think sum of arithmetic sequences, counting multiples, or date range calculations in production systems handling millions of records.