LC 1523.Count Odd Numbers in an Interval Range

题目描述

这是 LeetCode 上的 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

解答

方法一：数学

显然这是个数学问题，对 low 之后的奇数个数设为 x ，接下来我们分奇偶进行讨论：

1. 当 low 为奇数， high 为奇数时：\(low + 2x = high\)，自然就有 \(x = \frac{high - low}{2}\)，加上 low ，奇数个数为 \(x + 1\)。
2. 当 low 为奇数， high 为偶数时：\(low + 2x = high - 1\)，自然就有 \(x = \frac{high - low - 1}{2}\)，加上 low ，奇数个数为 \(x + 1\)。
3. 当 low 为偶数， high 为奇数时：\(low + 1 + 2x = high\)，自然就有 \(x = \frac{high - low - 1}{2}\)，加上 low + 1 ，奇数个数为 \(x + 1\)。
4. 当 low 为偶数， high 为偶数时： \(low + 1 + 2x = high - 1\)，自然就有 \(x = \frac{high - low - 2}{2}\)，加上 low + 1 奇数个数为 \(x + 1\)。

归纳上面的结果可以得到奇数的个数为 \(\frac{high - low - a}{2} + a\)，其中 a 为 low 和 high 两个数中奇数的个数。

由于上面的除法保证了分母一定为偶数，所以不需要担心除法是否整除的问题。

class Solution {
    public int countOdds(int low, int high) {
        int res = (low & 1) + (high & 1);
        return ((high - low - res) >> 1) + res;
    }
}

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

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

每题一图