LeetCode 1523 - Count Odd Numbers in an Interval Range

LeetCode Problem 1523

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem gives two non-negative integers, low and high, representing the inclusive bounds of an interval. We need to determine how many odd integers exist between these two values, including both endpoints.

An integer is odd if it is not divisible by 2. Examples of odd numbers are 1, 3, 5, and 7. Examples of even numbers are 0, 2, 4, and 6.

The input consists of:

• low, the starting value of the interval
• high, the ending value of the interval

The output should be a single integer representing the count of odd numbers in the range [low, high].

For example:

• If low = 3 and high = 7, the numbers in the interval are 3, 4, 5, 6, 7. The odd numbers are 3, 5, 7, so the answer is 3.
• If low = 8 and high = 10, the numbers are 8, 9, 10. Only 9 is odd, so the answer is 1.

The constraints are important:

• 0 <= low <= high <= 10^9

This tells us that the interval can be extremely large. A solution that iterates through every number in the range could potentially require up to one billion iterations, which is inefficient for such a simple counting problem. The constraints strongly suggest that we should derive the answer mathematically in constant time.

Several edge cases are important to consider:

• Both numbers are even
• Both numbers are odd
• One endpoint is odd and the other is even
• The interval contains exactly one number
• The interval starts at 0
• Very large ranges near 10^9

A correct implementation must handle all of these situations consistently.

Approaches

Brute Force Approach

The most direct solution is to iterate through every integer from low to high and check whether each number is odd.

A number is odd if number % 2 == 1. We can maintain a counter and increment it whenever we encounter an odd value.

This approach is correct because it explicitly examines every value in the interval and counts exactly the odd ones. However, it is inefficient for large ranges. If the interval contains millions or billions of numbers, iterating through all of them becomes unnecessarily slow.

Since the problem constraints allow values up to 10^9, we should avoid linear iteration.

Optimal Mathematical Approach

The key observation is that odd and even numbers alternate.

In any consecutive sequence of integers:

• Roughly half are odd
• Roughly half are even

We can determine the answer directly from the size of the interval.

First, compute the total number of integers in the range:

$$\text{count} = high - low + 1$$

Now consider two cases:

• If the interval length is even, exactly half the numbers are odd.
• If the interval length is odd, the parity of low determines whether there is one extra odd number.

An even simpler formulation is:

• Compute (high - low) // 2
• Add 1 if either endpoint arrangement guarantees an extra odd

A very elegant formula is:

$$\frac{high + 1}{2} - \frac{low}{2}$$

using integer division.

Another intuitive approach is:

• Total numbers = high - low + 1
• Base odd count = total // 2
• If total is odd and low is odd, add one more

This gives an O(1) solution with no iteration.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(high - low + 1)	O(1)	Iterates through every number and checks parity
Optimal	O(1)	O(1)	Uses mathematical properties of odd and even numbers

Algorithm Walkthrough

Optimal Algorithm

1. Compute the total number of integers in the interval using:

$$total = high - low + 1$$

This gives the inclusive size of the range. 2. Compute the base number of odd integers:

$$odd_count = total // 2$$

Since odd and even numbers alternate, half the numbers are odd in any evenly sized interval. 3. Check whether the interval length is odd.

If total % 2 == 1, there is one extra number that cannot be evenly paired. 4. If the interval length is odd, determine whether the extra number is odd.

Because the sequence alternates parity, the extra number has the same parity as low.

Therefore:

• If low is odd, add 1
• Otherwise, do nothing

5. Return the final count.

Why it works

Odd and even numbers alternate perfectly in consecutive integers. Every pair of adjacent numbers contains exactly one odd number. Therefore, for an interval of even length, exactly half the numbers are odd. For an interval of odd length, there is one additional number, and its parity matches the parity of the starting value. This guarantees that the formula always produces the correct count.

Python Solution

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        total_numbers = high - low + 1
        odd_count = total_numbers // 2

        if total_numbers % 2 == 1 and low % 2 == 1:
            odd_count += 1

        return odd_count

The implementation first computes the size of the interval using high - low + 1. The +1 is necessary because the range is inclusive.

Next, the code calculates total_numbers // 2. This gives the number of odd values in all complete odd-even pairs.

If the interval length is odd, one number remains unpaired. The parity of this extra number matches the parity of low, because parity alternates as we move through consecutive integers. Therefore, when both conditions are true:

• the interval length is odd
• low is odd

we add one additional odd number to the result.

Finally, the function returns the computed count.

Go Solution

func countOdds(low int, high int) int {
    totalNumbers := high - low + 1
    oddCount := totalNumbers / 2

    if totalNumbers%2 == 1 && low%2 == 1 {
        oddCount++
    }

    return oddCount
}

The Go implementation follows the exact same logic as the Python version.

One small language difference is that Go uses integer division automatically when dividing integers, so totalNumbers / 2 already truncates toward zero.

Since the problem constraints are at most 10^9, standard Go int values are completely safe and there is no risk of overflow.

Worked Examples

Example 1

Input:

low = 3
high = 7

The interval is:

3, 4, 5, 6, 7

Step	Variable	Value
Compute total numbers	total_numbers	7 - 3 + 1 = 5
Base odd count	odd_count	5 // 2 = 2
Is total odd?	5 % 2 == 1	Yes
Is low odd?	3 % 2 == 1	Yes
Add extra odd	odd_count	3

Final answer:

3

The odd numbers are:

3, 5, 7

Example 2

Input:

low = 8
high = 10

The interval is:

8, 9, 10

Step	Variable	Value
Compute total numbers	total_numbers	10 - 8 + 1 = 3
Base odd count	odd_count	3 // 2 = 1
Is total odd?	3 % 2 == 1	Yes
Is low odd?	8 % 2 == 1	No
Add extra odd?	No	odd_count = 1

Final answer:

1

The only odd number is:

9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations are performed
Space	O(1)	No additional data structures are used

The algorithm runs in constant time because it does not depend on the size of the interval. Whether the range contains 10 numbers or one billion numbers, the same fixed number of operations is executed. Space usage is also constant because only a few integer variables are stored.

Test Cases

solution = Solution()

assert solution.countOdds(3, 7) == 3  # Basic mixed interval
assert solution.countOdds(8, 10) == 1  # Only one odd number
assert solution.countOdds(0, 0) == 0  # Single even number
assert solution.countOdds(1, 1) == 1  # Single odd number
assert solution.countOdds(2, 2) == 0  # Single even value
assert solution.countOdds(5, 5) == 1  # Single odd value
assert solution.countOdds(2, 6) == 2  # Even to even interval
assert solution.countOdds(3, 9) == 4  # Odd to odd interval
assert solution.countOdds(4, 9) == 3  # Even to odd interval
assert solution.countOdds(1, 10) == 5  # Balanced interval
assert solution.countOdds(0, 10) == 5  # Includes zero
assert solution.countOdds(999999999, 1000000000) == 1  # Large boundary values
assert solution.countOdds(0, 1000000000) == 500000000  # Maximum range stress test

Test	Why
low=3, high=7	Standard example with multiple odd numbers
low=8, high=10	Standard example with one odd number
low=0, high=0	Smallest even interval
low=1, high=1	Smallest odd interval
low=2, high=2	Single even element
low=5, high=5	Single odd element
low=2, high=6	Even starting and ending points
low=3, high=9	Odd starting and ending points
low=4, high=9	Mixed parity endpoints
low=1, high=10	Balanced interval with equal odd/even split
low=0, high=10	Range including zero
low=999999999, high=1000000000	Large values near constraint limit
low=0, high=1000000000	Maximum range stress test

Edge Cases

Single Element Interval

When low == high, the interval contains exactly one number. This can easily expose off-by-one errors if the inclusive range calculation is incorrect.

For example:

low = 1, high = 1

The implementation handles this correctly because:

$$total = high - low + 1 = 1$$

The logic then correctly checks whether that single value is odd.

Both Endpoints Even

An interval where both endpoints are even can be tricky because the interval length may still be odd.

For example:

low = 8, high = 10

The interval length is 3, but only one number is odd. The implementation correctly handles this because when the interval length is odd, the extra number matches the parity of low. Since low is even, no extra odd number is added.

Very Large Ranges

The constraints allow values up to 10^9, which makes brute-force iteration impractical.

For example:

low = 0, high = 1000000000

A naive loop would require more than one billion iterations. The mathematical solution avoids iteration entirely and computes the result using only arithmetic operations, making it efficient even for the largest possible inputs.