#1523

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Count Odd Numbers in an Interval Range

Count Odd Numbers in an Interval Range efficiently using a math-driven formula that avoids unnecessary iteration over large ranges.

math

Problem Statement

Given two non-negative integers low and high, return the total count of odd numbers within the inclusive range [low, high]. This requires a math-driven solution without iterating through each number, ideal for large ranges.

For example, if low = 3 and high = 7, the odd numbers are [3, 5, 7], giving a total count of 3. Similarly, for low = 8 and high = 10, only 9 is odd, so the count is 1. Constraints ensure 0 <= low <= high <= 10^9.

Examples

Example 1

Input: low = 3, high = 7

Output: 3

The odd numbers between 3 and 7 are [3,5,7].

Example 2

Input: low = 8, high = 10

Output: 1

The odd numbers between 8 and 10 are [9].

Constraints

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

Solution Approach

Use endpoint parity to compute count

Check if low and high are odd or even. Use the formula (high + 1) // 2 - low // 2 to calculate the total odd numbers efficiently. This formula automatically accounts for the inclusive range and avoids loops.

Adjust for even-length ranges

If the interval length (high - low + 1) is even, the number of odd and even numbers is equal. This insight helps confirm correctness and simplifies edge cases where low or high is odd.

Constant time calculation

This approach works in O(1) time and O(1) space, handling the maximum range up to 10^9 instantly without iterating. Only simple arithmetic and integer division are required.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) because the count is calculated using a formula without iteration. Space complexity is O(1) as only a few integer variables are needed.

What Interviewers Usually Probe

Expect candidates to recognize parity and inclusive range handling.
Look for O(1) arithmetic-based solutions instead of loops.
Clarify edge cases when low or high is odd or even.

Common Pitfalls or Variants

Common pitfalls

Iterating through the entire range, which is unnecessary and inefficient.
Off-by-one errors when handling inclusive endpoints.
Miscounting when low and high are both odd or both even.

Follow-up variants

Count even numbers instead by adjusting the formula accordingly.
Count numbers divisible by k in a given interval using a similar math-driven approach.
Find the sum of odd numbers in the interval instead of just the count.

FAQ

What is the fastest way to count odd numbers in a range?

Use the formula (high + 1) // 2 - low // 2 to get the count in O(1) time without iterating.

Why does this problem rely on a math-driven solution strategy?

Iterating over large ranges can be slow; parity analysis and integer division provide instant counts, matching the math pattern.

How do I handle ranges where both endpoints are odd?

The formula automatically includes both endpoints when needed, so no extra checks are required.

Can this approach handle the maximum constraint of high = 10^9?

Yes, since the calculation uses only basic arithmetic, it works efficiently even for large values.

Is there a variant to count even numbers using this pattern?

Yes, swap the endpoints in the formula or calculate total numbers minus the odd count to get the even count instantly.

terminal

Solution

Solution 1: Prefix Sum Concept

We know that the count of odd numbers in the range $[0, x]$ is $\lfloor\frac{x+1}{2}\rfloor$. Therefore, the count of odd numbers in the range $[low, high]$ is $\lfloor\frac{high+1}{2}\rfloor - \lfloor\frac{low}{2}\rfloor$.

1

2

3

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        return ((high + 1) >> 1) - (low >> 1)

Continue Practicing

#1524 number of sub arrays with odd sum #1518 water bottles #1515 best position for a service centre