3827. Count Monobit Integers

📘 題目敘述

你會得到一個整數 n。

如果一個整數的二進位表示法中，所有 bit 都相同，則稱它為 Monobit。

請回傳在區間 [0, n]（包含 0 與 n）中，Monobit 整數的數量。

條件限制

• 0 <= n <= 1000

🧠 解題思路

Monobit 的意思是「二進位表示裡全部都是同一種 bit」。

在 0 <= n <= 1000 這個範圍內，我直接把所有可能是 Monobit 的數字先標記出來，再去數 [0, n] 裡有幾個被標記。

在這個範圍中會出現的 Monobit 數字其實很少：

• 0 的二進位是 "0"，所有 bit 相同，所以是 Monobit
• 1 的二進位是 "1"，所有 bit 相同，所以是 Monobit
• 其他 Monobit（全部都是 1 的那種）會長得像：
  • 3 = (11)_2
  • 7 = (111)_2
  • 15 = (1111)_2
  • …
  • 也就是 2^k - 1

因此我用一個迴圈從 3 開始，不斷做 i = 2*i + 1，就會依序得到 3, 7, 15, 31, ...，把它們標記成 Monobit，直接建立一個表。

最後再從 0 到 n 掃一次，把被標記的數量加總就是答案。

所有變數

• mon：長度 1001 的布林陣列，用來標記 0..1000 中哪些數是 Monobit
• count：統計 [0, n] 範圍內 Monobit 的個數

🪜 主要流程步驟

1. 先建立 Monobit 標記表

• 建立 mon[0..1000]，先全部設成 false
• 把 mon[0]、mon[1] 設成 true
• 從 3 開始，一直用 i = 2*i + 1 生成 3, 7, 15, ...，只要 i < 1001 就把 mon[i] = true

2. 統計 [0, n] 內有幾個被標記

• 從 0 掃到 n
• 如果 mon[j] == true，就把 count++

3. 回傳答案

• 回傳 count

💻 程式碼實作

class Solution {
public:
    int countMonobit(int n) {
        vector<bool> mon(1001, false);
        mon[0] = true;
        mon[1] = true;
        int count = 0;
        for (int i = 3; i < 1001; i = 2 * i + 1) {
            mon[i] = true;
        }
        for (int j = 0; j <= n; j++) {
            if (mon[j]) {
                count++;
            }
        }
        return count;
    }
};

🔗 題目連結

https://leetcode.com/problems/count-monobit-integers/