What is the main trick to solving Concatenation of Consecutive Binary Numbers efficiently?

The key is to treat the concatenation numerically by shifting the accumulated result left by the current number's bit length and adding the number, applying modulo at each step.

Why is using actual binary string concatenation inefficient?

Concatenating strings for large n consumes excessive memory and causes time limit exceeded errors; numeric shifting is faster and avoids building large strings.

How do you calculate the bit length needed for each shift?

Use log2 of the number or track when the number reaches a power of two, increasing the shift length accordingly.

Can this approach handle n = 100,000 without overflow?

Yes, applying modulo 10^9+7 at each step ensures the numeric result stays within integer bounds, even for very large n.

Does this problem pattern always involve both math and bit manipulation?

Yes, the core pattern requires combining math for shifts and modulo with bit manipulation for binary representation handling.

#1680

Medium

auto_awesome数学·位运算

LeetCode 题解工作台

连接连续二进制数字

给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的十进制数字对 10 9 + 7 取余的结果。示例 1：输入： n = 1 输出： 1 解释：二进制的 "1" 对应着十进制的 1 。示例 2：输入： n = 3 输出： 27 解释：二进制下，1，2 和…

数学位运算模拟

题目描述

给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 10⁹ + 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⁹ + 7 取余后，结果为 505379714 。

提示：

1 <= n <= 10⁵

lightbulb

解题思路

方法一：位运算

观察数字的连接规律，我们可以发现，当连接到第 $i$ 个数时，实际上是将前 $i-1$ 个数连接而成的结果 $ans$ 往左移动一定的位数，然后再加上 $i$ 这个数，移动的位数是 $i$ 中二进制的位数。

时间复杂度 $O(n)$ ，其中 $n$ 为给定的整数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        ans = 0
        for i in range(1, n + 1):
            ans = (ans << i.bit_length() | i) % mod
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each number requires a constant-time shift and addition with modulo. Space complexity is O(1) as no extra arrays or strings are stored, only the running result and temporary variables.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate immediately recognizes the problem as math plus bit manipulation with shifting and modulo.
question_mark
Candidate attempts naive string concatenation and is prompted to optimize using numeric shifts.
question_mark
Candidate considers overflow and applies modulo iteratively to maintain correctness.

warning

常见陷阱

外企场景

error
Trying to concatenate actual binary strings leads to memory inefficiency and TLE for large n.
error
Forgetting to shift the result by the correct bit length of the current number causes incorrect decimal values.
error
Neglecting modulo at each step results in integer overflow and wrong answers for large n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the concatenation in hexadecimal instead of decimal, still using bit manipulation to compute efficiently.
arrow_right_alt
Calculate the sum of the decimal values of all prefixes of the concatenated binary string.
arrow_right_alt
Compute the concatenation modulo a different prime, emphasizing modular arithmetic properties.

help

常见问题

外企场景

继续练习

#1688 比赛中的配对次数 #1799 N 次操作后的最大分数和 #1806 还原排列的最少操作步数