1523-在区间范围内统计奇数数目

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

示例 1：

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

示例 2：

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

提示：

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

方法一：前缀和思想

思路与算法

如果我们暴力枚举 {\rm [low, high] 中的所有元素会超出时间限制。

我们可以使用前缀和思想来解决这个问题，定义 {\rm pre}(x) 为区间 [0, x] 中奇数的个数，很显然：

{\rm pre}(x) = \lfloor x + 1/2} \rfloor

故答案为 \rm pre(high) - pre(low - 1)。

代码

[sol1-C++]

class Solution {
public:
    int pre(int x) {
        return (x + 1) >> 1;
    }
    
    int countOdds(int low, int high) {
        return pre(high) - pre(low - 1);
    }
};

[sol1-Java]

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

    public int pre(int x) {
        return (x + 1) >> 1;
    }
}

[sol1-Python3]

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        pre = lambda x: (x + 1) >> 1
        return pre(high) - pre(low - 1)

复杂度分析

• 时间复杂度：O(1)。

• 空间复杂度：O(1)。