Sponsored
Sponsored
This method leverages bit manipulation to efficiently construct the resulting number without physically concatenating binary strings. As each integer from 1 to n is processed, its binary representation is appended using bitwise operations, which helps avoid the overhead of string manipulation.
Time Complexity: O(n), because we process each number from 1 to n.
Space Complexity: O(1), as we use a fixed amount of additional space.
1def concatenatedBinary(n):
2 MOD = 10**9 + 7
3 result = 0
4 bit_length = 0
5 for i in range(1, n + 1):
6 # When i is a power of 2, increment the length of binary digits
7 if i & (i - 1) == 0:
8 bit_length += 1
9 result = ((result << bit_length) | i) % MOD
10 return resultIn this implementation, a loop iterates through each number from 1 to n. When the loop reaches a new power of 2, the binary length of numbers increases by one. Using left shift operations, we append the current number, then apply the modulo operation to keep the result manageable.
This naive strategy involves directly constructing the final binary string representation step by step. After forming the complete string, it converts it to an integer and performs modulo operation. This approach might be less efficient for large n due to string operations being costly.
Time Complexity: O(n * log n), as string operations for binary conversions dominate computation time.
Space Complexity: O(n * log n), due to the storage of the growing binary string.
public class Solution {
public int ConcatenatedBinary(int n) {
const int MOD = 1000000007;
System.Text.StringBuilder binaryString = new System.Text.StringBuilder();
for (int i = 1; i <= n; i++) {
binaryString.Append(Convert.ToString(i, 2));
}
long result = 0;
foreach (char ch in binaryString.ToString()) {
result = (result * 2 + (ch - '0')) % MOD;
}
return (int)result;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.ConcatenatedBinary(12));
}
}With C#, binary string collection is straightforward and then computationally simplified through conversion to numbered modulo applications.