Count Odd Numbers in an Interval Range
Maintained by Vikas D, software engineer
You are handed two non-negative integers, low and high, with low never larger than high. They mark the two ends of a closed interval, so both endpoints are part of the range you care about.
Your job is to report the count of odd numbers in that interval. An odd number is any integer that leaves a remainder of 1 when divided by 2, such as 1, 3, 5, and 7.
The endpoints can be either parity. low or high might themselves be odd, even, or equal to each other, and any of those should still produce the correct count.
The range can be huge (up to a billion), so walking through every value one at a time is too slow. The answer should come from arithmetic on low and high, not from iterating across the whole interval.
Examples
The odd values in [3, 7] are 3, 5, and 7, which is three numbers.
The odds are 1, 3, 5, 7, and 9. The even endpoint 10 contributes nothing.
A single even value sits in the range, so there are no odd numbers at all.
Constraints
- 0 <= low <= high <= 10^9
- Both low and high are inclusive endpoints of the interval.
- Both inputs are non-negative integers.
Visible test cases
- countOdds(3, 7) == 3
- countOdds(1, 10) == 5
- countOdds(2, 4) == 1
- countOdds(6, 6) == 0
- countOdds(0, 0) == 0
- countOdds(5, 5) == 1
- countOdds(0, 1000000000) == 500000000
Hints
Hint 1
Counting odds in a wide-open range is hard, but counting odds in [0, n] is a clean closed form. Work out how many odds live in [0, n] for any n.
Hint 2
In [0, n] there are exactly floor((n + 1) / 2) odd numbers. Check it: [0, 7] has 1, 3, 5, 7, which is floor(8 / 2) = 4.
Hint 3
Turn the interval into a difference of two prefixes. Odds in [low, high] equals odds in [0, high] minus odds in [0, low - 1].
Approaches
Brute force scan
Time O(high - low) · Space O(1)Walk every integer from low to high and tally the ones that are odd.
- Set a counter to zero.
- Loop n from low through high inclusive.
- If n is odd (n modulo 2 is 1), increment the counter.
- Return the counter after the loop ends.
Optimal prefix-count formula
Time O(1) · Space O(1)The number of odd values in [0, n] is floor((n + 1) / 2). Subtract the prefix count just below low from the prefix count at high.
- Define a helper oddsUpTo(n) that returns floor((n + 1) / 2), the count of odds in [0, n].
- Compute oddsUpTo(high) for the full upper prefix.
- Compute oddsUpTo(low - 1) for everything strictly below low.
- Return the first count minus the second; the overlap below low cancels out cleanly.
Common mistakes
- Forgetting that the range is inclusive on both ends and dropping high when it is odd.
- Using oddsUpTo(low) instead of oddsUpTo(low - 1), which double-removes low and undercounts by one when low is odd.
- Trying integer division on the raw width (high - low) without correcting for the parity of the endpoints, which is off by one in the cases where both ends are odd.
- Iterating element by element when high - low can reach a billion, which times out.
Follow-up variations
- Count even numbers in the same interval instead, or return both counts at once.
- Count multiples of an arbitrary k inside [low, high] using the same prefix-difference idea.
- Answer many [low, high] queries quickly, where the O(1) formula matters far more than the scan.
- Extend the range to allow negative endpoints and confirm the prefix formula still holds.