1523. Count Odd Numbers in an Interval Range - Explanation

Problem Link

Description

You are given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:

Input: low = 2, high = 9

Output: 4

Explanation: The odd numbers between 2 and 9 are [3,5,7,9].

Example 2:

Input: low = 9, high = 11

Output: 2

Explanation: The odd numbers between 9 and 11 are [9,11].

Example 2:

Input: low = 1, high = 1

Output: 1

Constraints:

• 0 <= low <= high <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

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

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Where $n$ is the number of integers in the given range.

---

2. Math

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

Time & Space Complexity

• Time complexity: $O(1)$
• Space complexity: $O(1)$

---

3. Math (One Liner)

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

Time & Space Complexity

• Time complexity: $O(1)$
• Space complexity: $O(1)$