題目

標題和出處

標題：連接連續二進制數字

出處：1680. 連接連續二進制數字

難度

5 級

題目描述

要求

給定一個整數 $\text{n}$，將 $\text{1}$ 到 $\text{n}$ 的二進制表示連接得到一個二進制數，返回連接得到的二進制數對應的十進制數對 ${\text{10}}^{\text{9}}+\text{7}$ 取余的結果。

示例

示例 1：

輸入：$\text{n?=?1}$
輸出：$\text{1}$
解釋：二進制的 $\text{"1"}$ 對應十進制的 $\text{1}$。

示例 2：

輸入：$\text{n?=?3}$
輸出：$\text{27}$
解釋：二進制下，$\text{1}$、$\text{2}$ 和 $\text{3}$ 分別對應 $\text{"1"}$、$\text{"10"}$ 和 $\text{"11"}$。
將它們依次連接，得到 $\text{"11011"}$，對應十進制的 $\text{27}$。

示例 3：

輸入：$\text{n?=?12}$
輸出：$\text{505379714}$
解釋：連接結果為 $\text{"1101110010111011110001001101010111100"}$，對應十進制的 $\text{118505380540}$。
對 ${\text{10}}^{\text{9}}+\text{7}$ 取余后，結果為 $\text{505379714}$。

數據范圍

• $\text{1}\le \text{n}\le {\text{10}}^{\text{5}}$

解法

思路和算法

由于 $1$ 到 $n$ 的二進制表示的連接結果可能很長，因此需要在遍歷連接結果的過程中計算結果。

初始時，連接結果是 $0$。當遍歷到整數 $i$ 時，假設 $1$ 到 $i?1$ 的連接結果對應的整數是 $x$，整數 $i$ 的二進制表示有 $\text{bits}$ 位，則 $1$ 到 $i?1$ 的連接結果對應的整數是將 $x$ 左移 $\text{bits}$ 位之后加 $i$。因此，只要知道 $1$ 到 $n$ 的每個整數的二進制表示的位數，即可得到連接的結果對應的整數。

如果正整數 $x$ 是 $2$ 的整數次冪，則 $x$ 的二進制表示的位數比 $x?1$ 的二進制表示的位數多 $1$，這里規定 $0$ 的二進制表示的位數是 $0$。正整數 $x$ 是 $2$ 的整數次冪等價于 $x\&(x?1)=0$，因此可以在 $O(1)$ 的時間內判斷一個整數是不是 $2$ 的整數次冪。

由此可以得到如下解法。

用 $\text{num}$ 表示連接結果，用 $\text{bits}$ 表示當前整數的二進制表示的位數，初始時 $\text{num}$ 和 $\text{bits}$ 都是 $0$。依次遍歷從 $1$ 到 $n$ 的每個整數，對于整數 $i$，執行如下操作。

1. 判斷 $i$ 是否是 $2$ 的整數次冪。如果 $i\&(i?1)=0$，則 $i$ 是 $2$ 的整數次冪，將 $\text{bits}$ 加 $1$，否則 $\text{bits}$ 不變。此時 $\text{bits}$ 是 $i$ 的二進制表示的位數。

2. 將 $\text{num}$ 的值更新為 $(\text{num}<<\text{bits})+i$，并將更新后的值對 $10^9+7$ 取余。

遍歷結束之后，$\text{num}$ 即為 $1$ 到 $n$ 的二進制表示的連接結果對應的整數。

需要注意的是，由于 $n$ 的最大值是 $10^5$，因此 $\text{bits}$ 的最大值是 $17$，$\text{nums}<<\text{bits}$ 的結果可能超出 $32$ 位整數的范圍。為了避免溢出，應將 $\text{num}$ 聲明為 $\text{long}$ 型，返回結果時轉成 $\text{int}$ 型。

代碼

class Solution {public int concatenatedBinary(int n) {final int MODULO = 1000000007;long num = 0;int bits = 0;for (int i = 1; i <= n; i++) {if ((i & (i - 1)) == 0) {bits++;}num = ((num << bits) + i) % MODULO;}return (int) num;}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是給定的整數。需要遍歷 $n$ 個整數，每個整數的操作時間都是 $O(1)$。

• 空間復雜度：$O(1)$。