Domain 1EasyCORE

Count Odd Numbers in an Interval Range

The problem asks us to count the number of odd numbers within a given range `[low, high]`, inclusive. The inputs are two non-negative integers `low` and `high`. The output should be an integer representing the count of odd numbers in this range.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

1523. Count Odd Numbers in an Interval Range

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 54.2%


Problem Breakdown

The problem asks us to count the number of odd numbers within a given range [low, high], inclusive. The inputs are two non-negative integers low and high. The output should be an integer representing the count of odd numbers in this range.

Inputs:

  • Two non-negative integers: low and high.

Outputs:

  • An integer representing the count of odd numbers between low and high.

Implicit Constraints or Edge Cases:

  • If low is equal to high, there’s only one number to check.
  • The range can be very large, up to 10^9.
  • Both low and high are non-negative.

Intuition

A brute-force approach would involve iterating through each number in the range [low, high] and checking if it is odd. This method has a time complexity of O(n), which is inefficient for large ranges like up to 10^9.

The key insight is that we can use mathematical properties to directly calculate the count of odd numbers without iterating through the entire range. The difference between consecutive odd numbers is always 2, so we can leverage this property to find the count more efficiently.

Approach

To solve this problem efficiently:

  1. Calculate the total number of integers in the range [low, high] using the formula: total_numbers = high - low + 1.
  2. Use integer division to determine how many complete pairs of even and odd numbers fit into the range.
  3. Adjust for any remaining numbers that might be odd.

The formula to calculate the count of odd numbers is:

  • If either low or high is odd, then add one to the result: count_of_odds = (high - low) // 2 + 1.
  • Otherwise, count_of_odds = (high - low) // 2.

Complexity Analysis

  • Time Complexity: O(1), because the solution involves only a few arithmetic operations and does not depend on the size of the input range.
  • Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

def countOdds(low: int, high: int) -> int:
    # Calculate the total number of integers in the range
    total_numbers = high - low + 1
    
    # If either low or high is odd, add one to the result
    if low % 2 == 1 or high % 2 == 1:
        return (high - low) // 2 + 1
    else:
        return (high - low) // 2

# Example usage:
# countOdds(3, 7) should return 3
# countOdds(8, 10) should return 1

Edge Cases Handled

  • Single Number Range: If low equals high, the function correctly returns 1 if the number is odd, or 0 if it’s even.
  • Large Ranges: The solution efficiently handles large ranges up to 10^9 without performance issues.
  • Even and Odd Boundaries: The function correctly adjusts for cases where either low or high (or both) are odd.