Problem Statement in English

You’re given two non-negative integers low and high. Return the count of odd numbers between low and high (both included).

Approach

To count the number of odd numbers in the interval [low, high], we can use a math forumla for arithmetic progressions.

$a_n = a_1 + (n-1) \cdot d$

Where:

  • $a_n$ is the last term (high)
  • $a_1$ is the first term (low)
  • $d$ is the common difference (2 for odd numbers)
  • $n$ is the number of terms (what we want to find)

Rearranging the formula to solve for n gives us:

$n = \frac{(a_n - a_1)}{d} + 1$

Solution in Python


class Solution:
    def countOdds(self, low: int, high: int) -> int:
        if not low % 2:
            low += 1
        
        if not high % 2:
            high -= 1

        n = ((high - low) // 2) + 1

        return n

Complexity

  • Time: $O(1)$
    Since we use a formula which requires no iteration over the input values.

  • Space: $O(1)$
    Since we use a constant amount of space.

And we are done.