📘 題目敘述
給你一個整數 n，請把 1 到 n 的二進位表示依序串接起來，形成一個很長的二進位字串。回傳這個二進位字串對應的十進位數值，並對 10^9 + 7 取模。
條件限制
1 <= n <= 10^5
🧠 解題思路
這題如果真的去建立那條很長的二進位字串再轉回十進位，長度會爆，而且成本很高。所以要改成「邊串邊算」的方式。
假設目前已經串好 1..(x-1) 的結果是 ans（十進位），現在要把 x 的二進位接到右邊。
如果 x 的二進位長度是 len，那把 x 接到右邊的十進位等價操作就是：
ans = ans * 2^len + x
原因是：在二進位往左移 len 位，等價於乘上 2^len，然後再加上 x 就是把它接在尾巴。
所以整題變成從 1 跑到 n，每次算出當前數字的 bit 長度 len，再做一次 ans = ans * 2^len + now，每一步都取模即可。
這份寫法重點是邏輯直觀：每次乘上 2^len 代表左移 len 格，再加上 now 就完成串接。
所有變數
c：模數1e9+7。ans：目前串接結果的十進位值（每一步都會取模）。now：目前要接上的數字（從 1 跑到 n）。len：now的 bit 長度，用(int)log2(now) + 1計算。
🪜 主要流程步驟
1. 初始化
ans = 0now = 1c = 1e9+7
2. 迴圈把 1 到 n 串起來
對每個 now：
- 計算
len = (int)log2(now) + 1 - 先把
ans左移len位：ans *= 2^len - 再把
now接到尾巴：ans += now - 取模：
ans %= c now++
3. 回傳答案
- 回傳
ans
⏱️ 複雜度
- 時間複雜度：
O(n)，從 1 到 n 每個數字處理一次。 - 空間複雜度：
O(1)，只使用固定數量變數。
💻 程式碼實作
class Solution {
public:
int concatenatedBinary(int n) {
const int c = 1000000007;
long long ans = 0;
int now = 1;
while (now <= n) {
ans *= pow(2, (int)log2(now) + 1);
ans += now;
ans %= c;
now++;
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/