Count Odd Numbers in an Interval Range

Problem Statement

The primary task is to determine the number of odd numbers that lie between two specified non-negative integers, including these two integers themselves. The two integers, termed as low and high, serve as the boundaries for this range. In essence, the function should return a count indicating how many numbers within this inclusive range are odd.

Examples

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 and Intuition

To solve this problem efficiently while considering the constraint limitations, observation and mathematical deduction are key. The constraints given (0 <= low <= high <= 10^9) suggest that a naive approach of iterating through each number between low and high would be computationally expensive, especially at the upper limits. Instead, a more mathematical approach can be applied:

1. Understanding Odd Number Counting:

   • Odd numbers are separated by even numbers. Between any two consecutive integers, one will always be even and the other odd, alternatively.

2. Starting Point Consideration:

   • If low is odd, the first number in our range is an odd number. If low is even, the count starts from the next number which will be odd.

3. Ending Point Consideration:

   • Similarly, if high is odd, it concludes our counting range on an odd number.

4. Calculating the Number of Odds Directly:

   • Calculate the number of odds between two consecutive integers directly:
     • If both low and high are odd, or both are even, the count of odd numbers from low to high is (high - low) / 2 + 1.
     • If one is odd and the other is even, then the count is (high - low) / 2.

This direct calculation does not require looping through all numbers from low to high, making it optimal even for the highest limits set by the constraints.

Solutions

class Solution {
public:
    int findOddCount(int min, int max) {
        if (!(min & 1)) {
            min++;
        }
        return min > max ? 0 : (max - min) / 2 + 1;
    }
};