Count Odd Numbers in an Interval Range

EasymathPrefix counting / closed-form mathmathcountingeasy

Maintained by Vikas Dulgunde, 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

Input: low = 3, high = 7

Output: 3

The odd values in [3, 7] are 3, 5, and 7, which is three numbers.

Input: low = 1, high = 10

Output: 5

The odds are 1, 3, 5, 7, and 9. The even endpoint 10 contributes nothing.

Input: low = 6, high = 6

Output: 0

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].

Loading the editor...

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.

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

Input: low = 3, high = 7

Output: 3

The odd values in [3, 7] are 3, 5, and 7, which is three numbers.

Input: low = 1, high = 10

Output: 5

The odds are 1, 3, 5, 7, and 9. The even endpoint 10 contributes nothing.

Input: low = 6, high = 6

Output: 0

A single even value sits in the range, so there are no odd numbers at all.

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.

Count Odd Numbers in an Interval Range

Examples

Constraints

Hints

Approaches

Brute force scan

Optimal prefix-count formula

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Count Odd Numbers in an Interval Range

Examples

Constraints

Hints

Approaches

Brute force scan

Optimal prefix-count formula

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep