Count Odd Numbers in an Interval Range

How it works

The count of odd numbers from 1 to n is (n + 1) / 2 (or equivalently (n + 1) >> 1). To find odd numbers in range [low, high], we take the count up to high and subtract the count below low. The count below low equals the count up to (low - 1), which is low / 2 or low >> 1.

Steps

1. Compute the number of odd integers from 1 to high: (high + 1) >> 1.
2. Compute the number of odd integers from 1 to (low - 1): low >> 1.
3. Subtract the second from the first to get odds in [low, high].
4. Return the result.

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Things to watch for

Off-by-One with Range Boundaries

When the range length is odd, whether you get an extra odd number depends on whether low (or high) is odd. Forgetting to check this boundary condition leads to undercounting by 1.

Using Division Without Considering Endpoints

Simply computing (high - low) / 2 ignores whether the range starts or ends on an odd number. The formula must account for the parity of the boundaries, not just the length.

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        return ((high + 1) >> 1) - (low >> 1)

class Solution {
public:
    int countOdds(int low, int high) {
        return ((high + 1) >> 1) - (low >> 1);
    }
};