{x}
blog image

Count Odd Numbers in an Interval Range

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

Solution Explanation

The problem asks to count the number of odd numbers within a given range [low, high], inclusive. A naive approach would iterate through the range and count odd numbers, but this is inefficient for large ranges. A much more efficient solution leverages bit manipulation and mathematical properties.

Core Idea:

The number of odd numbers in a range can be efficiently calculated by considering the number of odd and even numbers. The key observation is that roughly half the numbers in any range are odd (unless the range length is odd, in which case it's slightly more than half). We can determine the number of odd numbers without iterating.

Algorithm:

  1. Find the number of odd numbers up to high + 1: Right bit-shifting (>> 1) by 1 effectively divides a number by 2, discarding the remainder. If we apply this to high + 1, we get the number of odd numbers up to and including high + 1.

  2. Find the number of odd numbers up to low: Similarly, right bit-shifting low by 1 gives the number of odd numbers up to but excluding low.

  3. Subtract to find the number of odd numbers in the range: Subtracting the result of step 2 from step 1 provides the total number of odd numbers within the specified range [low, high].

Time and Space Complexity:

  • Time Complexity: O(1) - The solution performs a constant number of arithmetic operations regardless of the input range size. It doesn't involve iteration.

  • Space Complexity: O(1) - The solution uses a constant amount of extra space to store variables.

Code Explanation (Python as example, but the logic is identical across all languages):

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

The line return ((high + 1) >> 1) - (low >> 1) encapsulates the entire algorithm. Let's break it down:

  • (high + 1) >> 1: This calculates the number of odd numbers up to and including high. Adding 1 ensures that if high is odd, it's included in the count.

  • (low >> 1): This calculates the number of odd numbers up to but excluding low.

  • Subtracting the second expression from the first gives the number of odd numbers in the range [low, high].

The right bit shift (>> 1) is a highly efficient way to perform integer division by 2, making this solution incredibly fast even for very large ranges. This is faster than using the modulo operator (%) to check for odd numbers in a loop.