Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 109 + 7.
Example 1:
Input: n = 1 Output: 1 Explanation: "1" in binary corresponds to the decimal value 1.
Example 2:
Input: n = 3 Output: 27 Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11". After concatenating them, we have "11011", which corresponds to the decimal value 27.
Example 3:
Input: n = 12 Output: 505379714 Explanation: The concatenation results in "1101110010111011110001001101010111100". The decimal value of that is 118505380540. After modulo 109 + 7, the result is 505379714.
Constraints:
1 <= n <= 105Problem summary: Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Bit Manipulation
1
3
12
maximum-possible-number-by-binary-concatenation)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1680: Concatenation of Consecutive Binary Numbers
class Solution {
public int concatenatedBinary(int n) {
final int mod = (int) 1e9 + 7;
long ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans << (32 - Integer.numberOfLeadingZeros(i)) | i) % mod;
}
return (int) ans;
}
}
// Accepted solution for LeetCode #1680: Concatenation of Consecutive Binary Numbers
func concatenatedBinary(n int) (ans int) {
const mod = 1e9 + 7
for i := 1; i <= n; i++ {
ans = (ans<<bits.Len(uint(i)) | i) % mod
}
return
}
# Accepted solution for LeetCode #1680: Concatenation of Consecutive Binary Numbers
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
// Accepted solution for LeetCode #1680: Concatenation of Consecutive Binary Numbers
impl Solution {
pub fn concatenated_binary(n: i32) -> i32 {
let mod_: i64 = 1_000_000_007;
let mut ans: i64 = 0;
for i in 1..=n as i64 {
let bit_length: u32 = 64 - i.leading_zeros() as u32;
ans = ((ans << bit_length) | i) % mod_;
}
ans as i32
}
}
// Accepted solution for LeetCode #1680: Concatenation of Consecutive Binary Numbers
function concatenatedBinary(n: number): number {
const mod = 1_000_000_007;
let ans = 0;
for (let i = 1; i <= n; i++) {
ans = ((ans * (1 << (32 - Math.clz32(i)))) % mod + i) % mod;
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.