Count Odd Numbers in an Interval Range
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through each number in the given range from low to high. For each number, we perform a check to see if it is odd. A counter is maintained to keep track of the total count of odd numbers found.
Algorithm
- Initialize a counter variable
countto 0. - Loop through each integer
ifromlowtohigh(inclusive). - Inside the loop, check if
iis odd using the modulo operator (i % 2 != 0). - If
iis odd, incrementcount. - After the loop finishes, return
count.
Walkthrough
The algorithm is very straightforward:
- Initialize a counter variable,
count, to zero. - Create a loop that iterates from
lowtohigh, inclusive. - Inside the loop, for each number
i, use the modulo operator (%) to check if it's odd (i % 2 != 0). - If the number is odd, increment the
count. - After the loop completes, the
countvariable will hold the total number of odd integers in the range, which is then returned.
Here is the Java implementation:
class Solution { public int countOdds(int low, int high) { int count = 0; for (int i = low; i <= high; i++) { if (i % 2 != 0) { count++; } } return count; }}Complexity
Time
O(high - low). The time taken is directly proportional to the size of the interval. For large ranges (up to 10^9 as per constraints), this approach will be too slow and result in a Time Limit Exceeded (TLE) error.
Space
O(1). We only use a constant amount of extra memory for the counter and loop variable, regardless of the input range size.
Trade-offs
Pros
Very simple to understand and implement.
Works correctly for small ranges.
Cons
Highly inefficient for large ranges.
Will not pass the time constraints on most competitive programming platforms for this problem due to the large constraints (up to 10^9).
A much more efficient approach is to use a mathematical formula to calculate the result in constant time, avoiding any loops. The core idea is to find the count of odd numbers from 0 up to high and subtract the count of odd numbers from 0 up to low - 1.
Algorithm
- Calculate the count of odd numbers from 0 to
high:countHigh = (high + 1) / 2. - Calculate the count of odd numbers from 0 to
low - 1:countLow = low / 2. - The result is the difference:
countHigh - countLow. - Return the result.
Walkthrough
The number of positive odd integers less than or equal to a given non-negative integer n can be calculated with a simple formula: count = (n + 1) / 2. This works due to integer division.
For example:
- Odd numbers up to 7: [1, 3, 5, 7]. Count = 4.
(7 + 1) / 2 = 4. - Odd numbers up to 8: [1, 3, 5, 7]. Count = 4.
(8 + 1) / 2 = 9 / 2 = 4.
To find the number of odd numbers in the range [low, high], we can apply this logic:
- Calculate the number of odd integers from 0 up to
high. Let's call thisoddsUpToHigh. Using our formula,oddsUpToHigh = (high + 1) / 2. - Calculate the number of odd integers from 0 up to
low - 1. Let's call thisoddsUpToLowMinus1. Using our formula,oddsUpToLowMinus1 = ((low - 1) + 1) / 2 = low / 2. - The result is the difference between these two counts:
oddsUpToHigh - oddsUpToLowMinus1.
This method performs a few simple arithmetic operations and returns the result instantly, regardless of the size of the range.
Here is the Java implementation:
class Solution { public int countOdds(int low, int high) { // Count of odd numbers up to high is (high + 1) / 2 // Count of odd numbers up to low - 1 is low / 2 return (high + 1) / 2 - low / 2; }}Complexity
Time
O(1). The solution consists of a fixed number of arithmetic operations. The execution time is constant and does not depend on the values of `low` and `high`.
Space
O(1). No extra space is allocated that scales with the input size.
Trade-offs
Pros
Extremely efficient and fast.
Optimal solution for this problem.
Handles the entire range of constraints (up to 10^9) without any issues.
Cons
Requires some mathematical insight to derive the formula, making it slightly less intuitive than the brute-force method.
Solutions
Solution
class Solution { public int countOdds ( int low , int high ) { return (( high + 1 ) >> 1 ) - ( low >> 1 ); } }class Solution { public: int countOdds ( int low , int high ) { return ( high + 1 >> 1 ) - ( low >> 1 ); } };class Solution : def countOdds ( self , low : int , high : int ) -> int : return (( high + 1 ) >> 1 ) - ( low >> 1 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.