Problem Description

The Leetcode problem "Count Odd Numbers in an Interval Range" asks you to determine how many odd integers exist within a given inclusive interval. Specifically, you are given two integers, low and high, which define the start and end of the interval (both inclusive). Your task is to return the count of all odd numbers that are within this range.

• Both low and high are integers, and low <= high.
• The interval is inclusive, so both endpoints are considered.
• There is always exactly one valid solution for each input.
• The problem does not involve arrays or element reuse – it is purely about counting odds in a mathematical interval.

Thought Process

The first instinct when tackling this problem might be to iterate through every number from low to high and count how many of them are odd. This brute-force approach is straightforward, but it can be inefficient, especially if the interval is large.

However, since the task is to count (not list) the odd numbers, we can look for a mathematical shortcut. Odd numbers in any interval alternate with even numbers, so there is a predictable pattern. By leveraging simple arithmetic, we can avoid looping entirely and compute the answer in constant time.

The key is to realize that, for any two numbers, the total number of odd numbers between them can be calculated with a formula, rather than checking each value individually.

Solution Approach

Let's break down how to efficiently count the odd numbers in the interval [low, high]:

• Step 1: Calculate the total number of integers in the interval: high - low + 1.
• Step 2: Since odd and even numbers alternate, half of the numbers (rounded up) in any interval will be odd.
• Step 3: The formula (high - low) // 2 + 1 gives the count if either low or high is odd. If both are even, the count is (high - low) // 2.
• Step 4: Alternatively, a more concise formula is: (high + 1) // 2 - (low // 2). This works because (x + 1) // 2 gives the count of odd numbers from 1 to x, so subtracting gives the count in [low, high].
• Step 5: Implement this formula in code for efficiency and clarity.

This approach eliminates the need for loops and ensures the solution runs in constant time.

Example Walkthrough

Let's consider an example where low = 3 and high = 7.

• The numbers in the interval are: 3, 4, 5, 6, 7.
• The odd numbers are: 3, 5, 7.
• So, the expected answer is 3.
• Applying the formula: (high + 1) // 2 - (low // 2)
  • (7 + 1) // 2 = 8 // 2 = 4
  • 3 // 2 = 1
  • So, 4 - 1 = 3
• The formula correctly gives the count of odd numbers in the interval.

This process works for any interval, including those where low and high are both even, both odd, or one of each.

Code Implementation

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

class Solution {
public:
    int countOdds(int low, int high) {
        return (high + 1) / 2 - (low / 2);
    }
};
      

class Solution {
    public int countOdds(int low, int high) {
        return (high + 1) / 2 - (low / 2);
    }
}
      

/**
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var countOdds = function(low, high) {
    return Math.floor((high + 1) / 2) - Math.floor(low / 2);
};
      

Time and Space Complexity

• Brute-force Approach:
  • If you iterate from low to high and check each number, the time complexity is O(N), where N = high - low + 1.
  • Space complexity is O(1), as only a counter is needed.
• Optimized Formula Approach:
  • Time complexity is O(1) because it uses only a few arithmetic operations, regardless of the interval size.
  • Space complexity remains O(1).

The optimized approach is much faster and preferred, especially for large intervals.

Summary

In this problem, we leveraged the predictable alternation of odd and even numbers to derive a simple formula for counting odd numbers in any interval. Instead of iterating through the range, we used arithmetic to achieve a constant-time solution. This approach is both elegant and efficient, demonstrating how mathematical reasoning can simplify what might otherwise seem like a computational problem.