💬 Discord
Sign In
NeetCode #884LC-1523EasyMath & Geometry
← Back to All Problems

#884 · #1523 · Count Odd Numbers in an Interval Range(在区间范围内统计奇数数目)

📌 Problem Statement & Constraints

Given two non-negative integers low and high, return the number of odd integers in the inclusive range [low, high]. Constraints: 0 <= low <= high <= 10^9.

💡 Core Algorithmic Approaches

  1. The number of odd integers in [0, x] is (x + 1) // 2.
  2. By inclusion-exclusion the count in [low, high] is the count up to high minus the count up to low - 1.
  3. Substituting the formula and simplifying gives the closed form (high + 1) // 2 - low // 2.
  4. This is O(1); a loop over the range would be O(high - low), which can be 10^9 iterations.

💻 Benchmark Python3 Implementation

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        # odds in [0, high] minus odds in [0, low - 1]
        return (high + 1) // 2 - low // 2

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): a single arithmetic expression.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Iterating the range: O(high - low) is far too slow for the maximum bounds.
  • Using (high - low) // 2: this is off by one depending on the parities of the endpoints.
  • Writing (high - 1) // 2 - low // 2: the count-up-to function is (x + 1) // 2, not (x - 1) // 2.
  • Assuming low >= 1: the problem allows low = 0, which the formula handles correctly since 0 // 2 = 0.