Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 1523. Count Odd Numbers in an Interval Range

Return the number of odd integers in the inclusive interval [low, high]. The solution is a constant-time arithmetic count (no enumeration), suitable for large bounds up to 10^9.

Asked at:

Google

DESCRIPTION

Return the number of odd integers in the inclusive interval [low, high]. The solution is a constant-time arithmetic count (no enumeration), suitable for large bounds up to 10^9.

Input:

low = 3, high = 7

Output:

Explanation: The odd numbers in the range [3, 7] are 3, 5, and 7, so there are 3 odd integers

Constraints:

0 <= low <= high <= 10^9
The interval is inclusive on both ends
Solution must run in O(1) time (no enumeration allowed)

Understanding the Problem

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?

Brute Force Approach

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.

Visualization

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

Start counting odd numbers in range [3, 7]

0 / 18

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We iterate through every number in the range [low, high], where n = high - low + 1. For large ranges (e.g., 10^9 numbers), this becomes prohibitively slow

Space Complexity: O(1) We only use a constant amount of extra space for the counter variable, regardless of the range size

Building Intuition

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:

The total count of numbers in the range
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.

Common Mistakes

Attempting to iterate through the range: For large bounds like 10^9, this causes timeout. Always check if a mathematical formula exists before resorting to iteration

Incorrect handling of inclusive endpoints: The range [3, 7] includes both 3 and 7, so the total count is high - low + 1, not high - low. Forgetting the +1 leads to off-by-one errors

Not considering parity of endpoints: The formula differs slightly depending on whether low and high are both odd, both even, or mixed. Failing to check parity leads to incorrect counts in certain cases

Integer division truncation issues: In some languages, dividing odd numbers by 2 truncates the result. For example, 5 / 2 = 2 (not 2.5). Understanding how your language handles integer division is crucial for the formula to work correctly

Edge case of single-element range: When low == high, the range contains exactly one number. The formula must correctly return 1 if that number is odd, or 0 if it's even

Optimal Solution

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.

Visualization

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

Start counting odd numbers in range [3, 7]

0 / 8

Test Your Knowledge

Complexity Analysis

Time Complexity: O(1) We perform only a constant number of arithmetic operations (subtraction, division, modulo checks) regardless of the range size. Whether the range is [1,10] or [1,1000000000], the computation takes the same time

Space Complexity: O(1) We only use a constant amount of space to store the low, high values and the computed result. No data structures or arrays are needed

What We've Learned

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.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early September, 2024

Google

Junior

Find the number of odd numbers in an array

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 1523. Count Odd Numbers in an Interval Range

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact