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:
lowandhigh.
Outputs:
- An integer representing the count of odd numbers between
lowandhigh.
Implicit Constraints or Edge Cases:
- If
lowis equal tohigh, there’s only one number to check. - The range can be very large, up to
10^9. - Both
lowandhighare 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:
- Calculate the total number of integers in the range
[low, high]using the formula:total_numbers = high - low + 1. - Use integer division to determine how many complete pairs of even and odd numbers fit into the range.
- Adjust for any remaining numbers that might be odd.
The formula to calculate the count of odd numbers is:
- If either
loworhighis 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
lowequalshigh, 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^9without performance issues. - Even and Odd Boundaries: The function correctly adjusts for cases where either
loworhigh(or both) are odd.