Count Odd Numbers in an Interval Range

Difficulty: Easy | Acceptance: 54.50% | Paid: No Topics: Math

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

• Examples
• Constraints
• Brute Force
• Mathematical Formula

Examples

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 = 0, high = 10
Output: 5
Explanation: The odd numbers between 0 and 10 are [1,3,5,7,9].

Constraints

0 <= low <= high <= 10⁹

Brute Force

Intuition Iterate through all numbers from low to high and count how many are odd.

Steps

• Initialize a counter to 0
• Loop from low to high (inclusive)
• For each number, check if it’s odd using modulo operator
• Increment counter if odd
• Return the counter

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        count = 0
        for num in range(low, high + 1):
            if num % 2 == 1:
                count += 1
        return count

Complexity

• Time: O(n) where n = high - low + 1
• Space: O(1)
• Notes: Simple but inefficient for large ranges

Mathematical Formula

Intuition Use a mathematical formula to directly calculate the count of odd numbers without iteration. The count of odd numbers from 0 to n is (n + 1) / 2 using integer division. So the count from low to high is the count from 0 to high minus the count from 0 to low - 1.

Steps

• Calculate count of odd numbers from 0 to high: (high + 1) / 2
• Calculate count of odd numbers from 0 to low - 1: low / 2
• Return the difference

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Optimal solution with constant time complexity