花花酱 LeetCode 1523. Count Odd Numbers in an Interval Range

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

Example 1:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:

Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].

Constraints:

• 0 <= low <= high <= 10^9

Solution: Math

The count of odd numbers between [1, low – 1] is low / 2
e.g. low = 6, we have [1,3,5] in range [1, 5] and count is 6/2 = 3.
The count of odd numbers between [1, high] is (high + 1) / 2
e.g. high = 7, we have [1,3,5,7] in range [1, 7] and count is (7+1) / 2 = 4

Then the count of odd numbers in range [low, high] = count(1, high) – count(1, low-1)
e.g. in range [6, 7] we only have [7], count: 4 – 3 = 1

ans = (high + 1) / 2 – low / 2

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