Count Odd Numbers in an Interval Range

Problem Description

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Key Insights

• Odd numbers are integers that are not divisible by 2.
• The range is inclusive, meaning both low and high should be considered.
• The number of odd integers can be calculated directly using mathematical properties.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To count the odd numbers in the range from low to high, we can use the following approach:

1. Calculate the total count of numbers in the range, which is given by (high - low + 1).
2. Determine the first odd number in the range. If low is odd, the first odd number is low; if low is even, it is low + 1.
3. Determine the last odd number in the range. If high is odd, the last odd number is high; if high is even, it is high - 1.
4. If the first odd number is greater than the last odd number, there are no odd numbers in the range. Otherwise, the count of odd numbers can be computed using the formula: (last_odd - first_odd) / 2 + 1.

This approach uses basic arithmetic to achieve the result in constant time.

Code Solutions