1523. Count Odd Numbers in an Interval Range

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

1523Count Odd Numbers in an Interval RangeMath & GeometryEasyMath & Geometry

給定兩個非負整數 low 和 high，回傳 low 到 high（含）之間的奇數個數。

Example:

Input: low = 3, high = 7 Output: 3 (3, 5, 7)

Intuition

TIP

核心思路：用數學公式直接計算，不需要遍歷——[0, n] 中有 (n + 1) / 2 個奇數。

暴力遍歷 O(n) 太慢，需要 O(1) 的數學公式
[0, n] 中的奇數個數為 (n + 1) / 2（整數除法）
[low, high] 中的奇數個數 = [0, high] 的奇數數量 - [0, low-1] 的奇數數量

Approaches

1. Math Formula (prefix subtraction) — O(1) / O(1)

Idea: 利用 [0, n] 中奇數個數的公式，用前綴差計算區間內的奇數個數
Time: O(1)
Space: O(1)

class Solution {
    fun countOdds(low: Int, high: Int): Int {
        // [0, n] 中有 (n + 1) / 2 個奇數
        // [low, high] = [0, high] - [0, low - 1]
        return (high + 1) / 2 - low / 2
    }
}

⭐ 2. Intuitive Formula — O(1) / O(1)

Idea: 區間共 high - low + 1 個數，一半是奇數一半是偶數；如果端點任一為奇數則多一個奇數
Time: O(1)
Space: O(1)

class Solution {
    fun countOdds(low: Int, high: Int): Int {
        val count = high - low + 1
        return if (low % 2 == 1 || high % 2 == 1) {
            count / 2 + 1
        } else {
            count / 2
        }
    }
}

🔑 Takeaways

Pattern: 區間計數問題用前綴差公式 O(1) 求解
Key trick: (high + 1) / 2 - low / 2 是最簡潔的公式，利用整數除法的截斷特性

Intuition

Approaches

🔑 Takeaways

相關題目