Watch 10 video solutions for Count Odd Numbers in an Interval Range, a easy level problem involving Math. This walkthrough by NeetCodeIO has 8,962 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |