Jobs

Interviews

Discussions

Concatenation of Consecutive Binary Numbers

Medium

Asked by:

16 views

Topics:

Bit Manipulation

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⁹+ 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 10⁹ + 7, the result is 505379714.

Constraints:

1 <= n <= 10⁵

Try coding it in LeetCode

Concatenation of Consecutive Binary Numbers

Medium

Asked by:

16 views

Topics:

Bit Manipulation

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⁹+ 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 10⁹ + 7, the result is 505379714.

Constraints:

1 <= n <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n`? I want to understand the potential size of the resulting concatenated binary string.
Is the input `n` always a positive integer, or could it be zero or negative?
Are we expected to return the result as a standard integer type, or should I handle potential overflow issues by using a larger data type (e.g., long) or modular arithmetic?
Could you provide a small example of the input and expected output to ensure I fully understand the concatenation process?
Are there any specific constraints on memory usage, or can I assume that memory is not a limiting factor?

Brute Force Solution

Approach

The brute force method directly combines the binary representation of numbers from 1 to the given number. We convert each number to its binary form and stick them all together to form one big binary string. After that, we convert the whole binary string back to a number.

Here's how the algorithm would work step-by-step:

Start with an empty container to hold our combined binary string.
Take the first number, which is 1, and change it into its binary version: '1'. Add it to our container.
Now take the next number, 2, and convert it to binary: '10'. Add this to our container after the previous binary number.
Continue this process for all the numbers up to the number we were given, adding each number's binary equivalent to the end of the container.
Once we've added all the binary numbers, we have one big binary string.
Convert that giant binary string back into a single number (in base 10).
Return this final number.

Code Implementation

def concatenation_of_consecutive_binary_numbers_brute_force(number):    combined_binary_string = ""    # Build the combined binary string    for current_number in range(1, number + 1):        binary_representation = bin(current_number)[2:]        combined_binary_string += binary_representation    # Convert binary string to integer. We handle potential overflow.

    decimal_value = 0    power_of_two = 1    # Reverse traverse the binary string to compute
    # decimal value from binary representation.
    for bit in reversed(combined_binary_string):        if bit == '1':            decimal_value = (decimal_value + power_of_two) % (10**9 + 7)        power_of_two = (power_of_two * 2) % (10**9 + 7)    return decimal_value

Big(O) Analysis

Time Complexity

O(n log² n) – The algorithm iterates from 1 to n. In each iteration, converting a number 'i' to its binary representation takes O(log i) time, and appending it to the string takes O(log i) time, as the binary representation's length is proportional to log i. Summing this over all i from 1 to n gives us approximately n * log n for string construction. Converting the resulting binary string of length (sum of logs from 1 to n which is roughly n log n) to a decimal number takes time proportional to its length, hence O(n log n). Therefore, the overall time complexity is O(n log n + n log n), which simplifies to O(n log n). Since converting a binary string of length k to an integer takes O(k) time, and k = O(n log n), then the final conversion is O(n log n). Appending to the string is also O(log n) for each number, so the total string construction is O(n log n). Therefore the total is O(n log n). However, when converting the final large binary string to decimal, each digit multiplication and addition requires multiplying an integer and adding it to another which is an O(log n) time operations because integers can grow as big as n. There are O(n log n) such operations, thus the conversion becomes O(n log² n). The loop combined with the final string conversion makes it O(n log² n).

Space Complexity

O(N log N) – The dominant space complexity comes from concatenating the binary strings of numbers from 1 to N. Each number i (where 1 <= i <= N) has a binary representation of length at most log(i). Summing up these lengths for all i from 1 to N gives us a total binary string length of approximately N log N. This large string, held in memory as the combined binary string, determines the auxiliary space. The space required to store this concatenated string grows proportionally with N log N, therefore the auxiliary space complexity is O(N log N).

Optimal Solution

Approach

The problem asks us to combine the binary representations of numbers. The key is to realize we don't actually need to generate the binary strings, which would be slow. We can cleverly calculate the number of bits each number will occupy in its binary form and use that to shift our running result leftward, making space for the next number's bits.

Here's how the algorithm would work step-by-step:

Start with a running total initialized to zero.
Go through the numbers one by one, from 1 up to the target number.
For each number, figure out how many bits are needed to represent it in binary.
Shift the running total to the left by that many bits. This is like multiplying the running total by 2 raised to the power of the number of bits.
Add the current number to the shifted running total.
Take the result and perform a modulo operation with a large prime number. This keeps the result within manageable bounds.
After processing all the numbers, the running total is the final answer.

Code Implementation

def concatenated_binary(target_number):
    running_total = 0
    modulo = 10**9 + 7

    for number in range(1, target_number + 1):
        # Determine number of bits in binary representation
        number_of_bits = number.bit_length()

        # Shift running total left to make space
        running_total <<= number_of_bits

        # Add the current number
        running_total += number

        # Apply modulo to keep within bounds
        running_total %= modulo

    return running_total

Big(O) Analysis

Time Complexity

O(n) – The code iterates from 1 to n in a single loop. Inside the loop, the number of bits required to represent the current number in binary is calculated, a left bit shift is performed, an addition is done, and a modulo operation is performed. All operations inside the loop take constant time, independent of n. Therefore, the time complexity is dominated by the single loop that runs n times, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm uses a single running total variable to accumulate the result and a variable to store the number of bits for each number. These variables take up constant space regardless of the input number N. No auxiliary data structures like arrays or hash maps are created, and the recursion depth is constant (not recursive). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Input n is 0	Return 0 as per the problem statement or define the desired behavior for 0.
Input n is 1	Return 1 directly, as the concatenated binary string will simply be '1'.
Input n is a large number approaching the maximum integer value	Consider potential integer overflow when calculating the concatenated binary string length and handle using modulo arithmetic or appropriate data types such as long.
Calculating the number of bits for large n, where the log2 might have floating point precision issues	Use bit manipulation methods (like repeatedly right-shifting) for calculating the number of bits instead of relying on floating point operations.
Potential timeout for extremely large 'n' values	Optimize the calculation by minimizing operations within the loop, focusing on bit manipulation instead of string concatenation.
Integer Overflow during left bit shift operations	Apply the modulo operator after each left bit shift operation to prevent integer overflow.
Edge case where n is power of 2 minus one	Handle powers of 2 efficiently since these can result in longest bit lengths.
n is a negative number	Raise an exception or return 0 as the input is not valid according to the problem definition.

Input n is 0

How to Handle:

Return 0 as per the problem statement or define the desired behavior for 0.

Input n is 1

How to Handle:

Return 1 directly, as the concatenated binary string will simply be '1'.

Input n is a large number approaching the maximum integer value

How to Handle:

Consider potential integer overflow when calculating the concatenated binary string length and handle using modulo arithmetic or appropriate data types such as long.

Calculating the number of bits for large n, where the log2 might have floating point precision issues

How to Handle:

Use bit manipulation methods (like repeatedly right-shifting) for calculating the number of bits instead of relying on floating point operations.

Potential timeout for extremely large 'n' values

How to Handle:

Optimize the calculation by minimizing operations within the loop, focusing on bit manipulation instead of string concatenation.

Integer Overflow during left bit shift operations

How to Handle:

Apply the modulo operator after each left bit shift operation to prevent integer overflow.

Edge case where n is power of 2 minus one

How to Handle:

Handle powers of 2 efficiently since these can result in longest bit lengths.

n is a negative number

How to Handle:

Raise an exception or return 0 as the input is not valid according to the problem definition.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n`? I want to understand the potential size of the resulting concatenated binary string.
Is the input `n` always a positive integer, or could it be zero or negative?
Are we expected to return the result as a standard integer type, or should I handle potential overflow issues by using a larger data type (e.g., long) or modular arithmetic?
Could you provide a small example of the input and expected output to ensure I fully understand the concatenation process?
Are there any specific constraints on memory usage, or can I assume that memory is not a limiting factor?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty container to hold our combined binary string.
Take the first number, which is 1, and change it into its binary version: '1'. Add it to our container.
Now take the next number, 2, and convert it to binary: '10'. Add this to our container after the previous binary number.
Continue this process for all the numbers up to the number we were given, adding each number's binary equivalent to the end of the container.
Once we've added all the binary numbers, we have one big binary string.
Convert that giant binary string back into a single number (in base 10).
Return this final number.

Code Implementation

def concatenation_of_consecutive_binary_numbers_brute_force(number):    combined_binary_string = ""    # Build the combined binary string    for current_number in range(1, number + 1):        binary_representation = bin(current_number)[2:]        combined_binary_string += binary_representation    # Convert binary string to integer. We handle potential overflow.

    decimal_value = 0    power_of_two = 1    # Reverse traverse the binary string to compute
    # decimal value from binary representation.
    for bit in reversed(combined_binary_string):        if bit == '1':            decimal_value = (decimal_value + power_of_two) % (10**9 + 7)        power_of_two = (power_of_two * 2) % (10**9 + 7)    return decimal_value

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a running total initialized to zero.
Go through the numbers one by one, from 1 up to the target number.
For each number, figure out how many bits are needed to represent it in binary.
Shift the running total to the left by that many bits. This is like multiplying the running total by 2 raised to the power of the number of bits.
Add the current number to the shifted running total.
Take the result and perform a modulo operation with a large prime number. This keeps the result within manageable bounds.
After processing all the numbers, the running total is the final answer.

Code Implementation

def concatenated_binary(target_number):
    running_total = 0
    modulo = 10**9 + 7

    for number in range(1, target_number + 1):
        # Determine number of bits in binary representation
        number_of_bits = number.bit_length()

        # Shift running total left to make space
        running_total <<= number_of_bits

        # Add the current number
        running_total += number

        # Apply modulo to keep within bounds
        running_total %= modulo

    return running_total

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 0	Return 0 as per the problem statement or define the desired behavior for 0.
Input n is 1	Return 1 directly, as the concatenated binary string will simply be '1'.
Input n is a large number approaching the maximum integer value	Consider potential integer overflow when calculating the concatenated binary string length and handle using modulo arithmetic or appropriate data types such as long.
Calculating the number of bits for large n, where the log2 might have floating point precision issues	Use bit manipulation methods (like repeatedly right-shifting) for calculating the number of bits instead of relying on floating point operations.
Potential timeout for extremely large 'n' values	Optimize the calculation by minimizing operations within the loop, focusing on bit manipulation instead of string concatenation.
Integer Overflow during left bit shift operations	Apply the modulo operator after each left bit shift operation to prevent integer overflow.
Edge case where n is power of 2 minus one	Handle powers of 2 efficiently since these can result in longest bit lengths.
n is a negative number	Raise an exception or return 0 as the input is not valid according to the problem definition.

Input n is 0

How to Handle:

Return 0 as per the problem statement or define the desired behavior for 0.

Input n is 1

How to Handle:

Return 1 directly, as the concatenated binary string will simply be '1'.

Input n is a large number approaching the maximum integer value

How to Handle:

Consider potential integer overflow when calculating the concatenated binary string length and handle using modulo arithmetic or appropriate data types such as long.

Calculating the number of bits for large n, where the log2 might have floating point precision issues

How to Handle:

Use bit manipulation methods (like repeatedly right-shifting) for calculating the number of bits instead of relying on floating point operations.

Potential timeout for extremely large 'n' values

How to Handle:

Optimize the calculation by minimizing operations within the loop, focusing on bit manipulation instead of string concatenation.

Integer Overflow during left bit shift operations

How to Handle:

Apply the modulo operator after each left bit shift operation to prevent integer overflow.

Edge case where n is power of 2 minus one

How to Handle:

Handle powers of 2 efficiently since these can result in longest bit lengths.

n is a negative number

How to Handle:

Raise an exception or return 0 as the input is not valid according to the problem definition.