Count Odd Numbers in an Interval Range - Solution & Explanation
Problem Statement
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^9
Approach Overview
Problem 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 1: Mathematical Pattern Approach
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.
Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Approach 2: Iterative Checking Approach
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.
Complexity
Time Complexity: O(n), where n is (high - low + 1)
Space Complexity: O(1)
Approach 3: 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.
The time complexity is O(1), and the space complexity is O(1).
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python • NeetCodeIO • 9,212 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Odd Numbers in an Interval Range easy or hard?
Count Odd Numbers in an Interval Range Python/Java solution
How to solve Count Odd Numbers in an Interval Range in O(1)?
What is the best approach for Count Odd Numbers in an Interval Range?
Is Count Odd Numbers in an Interval Range asked at Google/Amazon/Meta?
What data structure is used in Count Odd Numbers in an Interval Range?
What is the time complexity of Count Odd Numbers in an Interval Range?
Ready to solve this problem?
Practice Count Odd Numbers in an Interval Range with our built-in code editor and test cases.
Practice on FleetCode