We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Concatenation of Consecutive Binary Numbers

Difficulty: Medium

Problem Description

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 10^9 + 7.

Key Insights

  • The binary representation of numbers can vary in length, which needs to be accounted for when concatenating.
  • The result must be computed modulo 10^9 + 7 to avoid overflow and to meet problem constraints.
  • Efficiently managing the bit-length of each number can help in shifting the current result correctly when concatenating.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The problem can be solved using a simple loop that iterates through each integer from 1 to n. For each integer, we convert it to its binary representation, calculate its length, and then update the result by shifting the current result left by the length of the binary representation and adding the new integer's value. Finally, we take the modulo at each step to ensure we do not encounter overflow.

Code Solutions

def concatenatedBinary(n: int) -> int:
    MOD = 10**9 + 7
    result = 0
    for i in range(1, n + 1):
        # Get the number of bits required for the current number
        length = i.bit_length()  
        # Shift the result left and add the current number
        result = ((result << length) | i) % MOD  
    return result
← Back to All Questions