原文链接: https://leetcode-cn.com/problems/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

中文题目

给你两个非负整数 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 \frac{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)$。

统计信息

通过次数	提交次数	AC比率
10498	18224	57.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言