Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).
Example 1:
Input: low = 3, high = 7 Output: 3 Explanation: The odd numbers between 3 and 7 are [3,5,7].
Example 2:
Input: low = 8, high = 10 Output: 1 Explanation: The odd numbers between 8 and 10 are [9].
Constraints:
0 <= low <= high <= 10^9Problem Overview: Given two integers low and high, determine how many odd numbers exist in the inclusive range [low, high]. The challenge is identifying a quick way to count odd numbers without scanning every value when the range becomes large.
Approach 1: Iterative Checking Approach (O(n) time, O(1) space)
The straightforward solution iterates from low to high and checks each number. A number is odd if num % 2 != 0. Maintain a counter and increment it whenever an odd value appears. This approach uses a simple loop and constant extra memory, making it easy to implement and useful for demonstrating understanding of basic math properties and modulo checks.
The drawback is scalability. If the interval spans millions or billions of numbers, iterating through every value becomes inefficient. Time complexity grows linearly with the range size, which interviewers typically expect you to optimize.
Approach 2: Mathematical Pattern Approach (O(1) time, O(1) space)
Odd and even numbers alternate. Every pair of consecutive integers contributes exactly one odd number. The total count of numbers in the range is high - low + 1. If this count is even, exactly half are odd. If it is odd, whether the extra number is odd depends on the starting value.
The optimized formula becomes: (high + 1) // 2 - low // 2. This works because dividing an integer by two using integer division effectively counts how many odd numbers exist up to that value. Subtracting the counts gives the number of odds within the interval.
This constant-time calculation eliminates iteration entirely. It relies purely on arithmetic properties of integers and parity, which is why it often appears in math or number theory problem sets. The solution is also extremely concise and works efficiently even for very large ranges.
Recommended for interviews: The mathematical pattern approach is the expected solution. Interviewers typically want to see whether you recognize the alternating pattern of odd and even numbers and reduce the problem to a simple arithmetic formula. The iterative method shows baseline reasoning, but the O(1) mathematical solution demonstrates stronger problem-solving and pattern recognition.
This approach uses the mathematical properties of odd and even numbers. The core idea is to count the odd numbers in the range efficiently without iterating through all numbers.
Two cases arise:
- If both low and high are odd, then the range includes both `low` and `high` as odd numbers.
- Otherwise, depending on whether `low` or `high` is even, you adjust the start or the end.
The formula used is derived from these observations:
If either `low` or `high` is odd, the count is `(high - low) / 2 + 1`. Otherwise, it is `(high - low) / 2`.
This C solution uses integer arithmetic to calculate the number of odd numbers directly. The expression (high + 1) / 2 gives the count of odd numbers from 1 to high, and low / 2 gives the count of odd numbers from 1 up to just below low. Their difference provides the count of odd numbers between low and high.
Time Complexity: O(1)
Space Complexity: O(1)
In this approach, we iterate through the numbers from low to high and check if each number is odd by using the modulus operator. Count every number that meets the condition of being odd.
This approach, though straightforward, is less optimal for larger ranges due to its linear nature in terms of time complexity.
This C solution uses a for-loop to iterate between the low and high values, incrementing a counter whenever it encounters an odd number as determined by the modulus operator.
Time Complexity: O(n), where n is (high - low + 1)
Space Complexity: O(1)
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.
The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Mathematical Pattern Approach | Time Complexity: O(1) Space Complexity: O(1) |
| Iterative Checking Approach | Time Complexity: O(n), where n is (high - low + 1) Space Complexity: O(1) |
| Prefix Sum Concept | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Checking | O(n) | O(1) | Useful for beginners or when demonstrating basic iteration and modulo checks |
| Mathematical Pattern | O(1) | O(1) | Best for interviews and large ranges where iterating through every number would be inefficient |
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python • NeetCodeIO • 8,962 views views
Watch 9 more video solutions →Practice Count Odd Numbers in an Interval Range with our built-in code editor and test cases.
Practice on FleetCode