Count Odd Numbers In An Interval Range

---

Intuition

• This problem can be naively solved by checking if each number from low to high inclusive mod 2 equals 1.
• We can optimize this with some math. Notice that there will always be the floor of high - low + 1 divided by 2 elements that are odd. However, if you start and end at an odd number, there is one more than that.
  • ex) 3, 4, 5 gives 2
• We say there are high - low + 1 points specifically because if you imagine a number line, high - low represents the number of points needed to get to high, but does not include high itself.

Complexity

Runtime

$O(1)$

Space

$O(1)$

Code

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        n = high - low + 1
        div = n // 2
        if low % 2 == 1 and n % 2 == 1:
            div += 1
        return div

Notes

Cards

START Basic Front: Count Odd Numbers In An Interval Range Back: Notice how many odd numbers there are when starting from odd number versus even number. END

---

References

• Count Odd Numbers In An Interval Range
• ChatGPT