题目描述

给你两个非负整数 low 和 high。请你返回 low 和 high 之间（包括二者）奇数的数目。

样例

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7]。

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9]。

限制

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

算法

(数学) $O(1)$

1. 如果区间长度为奇数且区间起点（或终点）也是奇数，则奇数的数目为区间长度除以 2 上取整。
2. 其余情况，奇数的数目为区间长度除以 2 下取整。

时间复杂度

• 仅一步计算，故时间复杂度为 $O(1)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int countOdds(int low, int high) {
        int cnt = high - low + 1;
        if (cnt & 1)
            return (cnt >> 1) + (low & 1);

        return cnt >> 1;
    }
};