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.
1#include <iostream>
2using namespace std;
3
4class Solution {
5public:
6 int concatenatedBinary(int n) {
7 const int MOD = 1000000007;
8 long result = 0;
9 int bitLength = 0;
10 for (int i = 1; i <= n; i++) {
11 if ((i & (i - 1)) == 0) bitLength++;
12 result = ((result << bitLength) | i) % MOD;
13 }
14 return (int)result;
15 }
16};This C++ implementation utilizes the same logic for handling bit operations as other solutions. It efficiently manages the growing binary numbers using shifts, accumulates results, and keeps operations modulated.
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.
String concatenation of binaries in JavaScript is straightforward and straightforwardly translated back into result manipulation with modulo operations safeguarding overflow.