題目

給你一個整數 n ，請你將 1 到 n 的二進位制表示連線起來，

並返回連線結果對應的 十進位制 數字對 109 + 7 取餘的結果。

示例 1：輸入：n = 1 輸出：1

解釋：二進位制的 "1" 對應著十進位制的 1 。

示例 2：輸入：n = 3 輸出：27

解釋：二進位制下，1，2 和 3 分別對應 "1" ，"10" 和 "11" 。

將它們依次連線，我們得到 "11011" ，對應著十進位制的 27 。

示例 3：輸入：n = 12 輸出：505379714

解釋：連線結果為 "1101110010111011110001001101010111100" 。

對應的十進位制數字為 118505380540 。

對 10^9 + 7 取餘後，結果為 505379714 。

提示：1 <= n <= 10^5

解題思路分析

1、遍歷；時間複雜度O(n)，空間複雜度O(1)

func concatenatedBinary(n int) int {	res := 0	for i := 1; i <= n; i++ {		length := bits.Len(uint(i))		res = (res<<length + i) % 1000000007	}	return res}

2、遍歷；時間複雜度O(n)，空間複雜度O(1)

func concatenatedBinary(n int) int {	res := 0	length := 0	for i := 1; i <= n; i++ {		if i&(i-1) == 0 {			length++		}		res = (res<<length + i) % 1000000007	}	return res}

總結

Medium題目，按照題目意思進行遍歷，遍歷的時候先左移然後求和