Count Odd Numbers in an Interval Range

easy math

Problem

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

Inputlow = 3, high = 7

Output3

The odd numbers between 3 and 7 are 3, 5, 7.

low

high

def count_odds(low, high):
    return (high + 1) // 2 - low // 2

function countOdds(low, high) {
  return ((high + 1) >> 1) - (low >> 1);
}

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

int countOdds(int low, int high) {
    return ((high + 1) / 2) - (low / 2);
}

Explanation

Instead of looping through the range and checking each number, we count the odds with a single formula based on a neat counting trick.

The key fact: the count of odd numbers in [1, x] is exactly (x + 1) / 2 using integer division (which throws away the fractional part). For example, in [1, 7] the odds are 1, 3, 5, 7, and (7 + 1) / 2 = 4.

To get the odds in [low, high], we count odds up to high and subtract the odds below low: (high + 1) / 2 - low / 2. The low / 2 piece counts odds in [1, low - 1], so subtracting removes everything before the start of our range.

Example: low = 3, high = 7. Odds up to 7 is (7 + 1) / 2 = 4. Odds below 3 is 3 / 2 = 1 (just the number 1). The answer is 4 - 1 = 3, which are 3, 5, 7.

Since this is just a bit of arithmetic, it runs in constant time no matter how huge the range is.

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