Count Odd Numbers in an Interval Range: A Math Shortcut

LeetCode 1523, Count Odd Numbers in an Interval Range, asks you to count how many odd numbers fall between two given integers. It looks like a loop problem, but the real solution is a one-liner that runs in constant time.

The problem

Given two non-negative integers low and high, return the count of odd numbers between low and high (inclusive).

For example, with low = 3 and high = 7, the numbers in the range are 3, 4, 5, 6, 7. The odd ones are 3, 5, and 7, so the answer is 3.

The brute force approach

The most obvious solution is to loop from low to high and count every odd number:

def countOdds(low, high):
    count = 0
    for num in range(low, high + 1):
        if num % 2 != 0:
            count += 1
    return count

This works, but it visits every number in the range. If high - low is large (up to 10^9 according to the constraints), this loop will time out. You need a way to jump straight to the answer.

The key insight

Odd and even numbers alternate perfectly on the number line: odd, even, odd, even, and so on. That regularity means you can count them with arithmetic instead of iteration.

The number of odd integers from 1 to n is (n + 1) // 2. Think of it this way: in the sequence 1, 2, 3, ..., n, roughly half the values are odd. Floor division handles the off-by-one for you.

To count odds in a range [low, high], count the odds from 1 to high and subtract the odds from 1 to low - 1:

odds in [low, high] = (high + 1) // 2 - low // 2

Notice that (low - 1 + 1) // 2 simplifies to low // 2. That is the entire formula.

Step-by-step walkthrough

The code

def countOdds(low, high):
    return (high + 1) // 2 - low // 2

That is the entire solution. (high + 1) // 2 gives the count of odd numbers from 1 to high. low // 2 gives the count of odd numbers from 1 to low - 1. The difference is the count of odd numbers in [low, high].

No loops, no conditionals, no extra variables. Just two floor divisions and a subtraction.

Complexity analysis

The brute force approach iterates through every number in the range. With constraints allowing up to 10^9 values, that is far too slow. The math formula computes the answer with two integer divisions and one subtraction, regardless of how large the range is.

The building blocks

Counting with floor division

Many problems ask "how many multiples of k are there from a to b?" or "how many values satisfy some periodic property in a range?" The technique is always the same: count from 1 to b, count from 1 to a - 1, and subtract. Floor division handles the counting because periodic patterns (every other number, every third number, etc.) map cleanly to integer arithmetic.

# Count multiples of k in [a, b]
count = b // k - (a - 1) // k

Odd numbers are just the special case where k = 2 and you count the values that are not divisible by 2. The formula (n + 1) // 2 is equivalent to ceil(n / 2), which counts the odd values from 1 to n.

Prefix count subtraction

The pattern of computing f(high) - f(low - 1) to get a range answer appears everywhere. It is the same idea behind prefix sums, range frequency queries, and cumulative distribution functions. Whenever a quantity accumulates monotonically, you can get any subrange by subtracting two prefix values.

Edge cases

Both endpoints are the same and odd. If low = high = 5, then (5 + 1) // 2 - 5 // 2 = 3 - 2 = 1. Correct: the single number 5 is odd.

Both endpoints are the same and even. If low = high = 4, then (4 + 1) // 2 - 4 // 2 = 2 - 2 = 0. Correct: the single number 4 is not odd.

Range of size 1 with low = 0. If low = 0 and high = 0, then (0 + 1) // 2 - 0 // 2 = 0 - 0 = 0. Zero is even, so the count is 0.

Large range. If low = 0 and high = 1000000000, the formula computes 500000000 - 0 = 500000000 instantly. No loop could handle this in time.

Both endpoints odd. If low = 3 and high = 9, then (9 + 1) // 2 - 3 // 2 = 5 - 1 = 4. The odd numbers 3, 5, 7, 9 confirm this.

From understanding to recall

This problem is deceptively simple. In a calm setting, the formula is obvious. But under interview pressure, you might blank on whether it is (n + 1) // 2 or n // 2, or whether you subtract low // 2 or (low - 1) // 2. These small details matter and are easy to confuse.

The fix is not to memorize the formula. It is to internalize the building block: counting periodic values in a range via prefix subtraction. Once that pattern is second nature, you derive the formula on the spot in seconds. You count odds up to high, count odds below low, and subtract. Done.

Spaced repetition drills this derivation at increasing intervals until it is automatic. When a range-counting question appears in your interview, you do not fumble with off-by-one errors. You write the one-liner and move on.

Related posts

• Count Primes - Counting with math formulas. Uses a sieve instead of floor division, but the core idea of avoiding brute force counting is the same.
• Missing Number - Math-based counting with the Gauss sum formula. Another problem where arithmetic replaces iteration.
• Sum of Even Numbers After Queries - Parity-based counting and tracking even/odd values incrementally.