1680. Concatenation of Consecutive Binary Numbers LeetCode Solution
In this guide, you will get 1680. Concatenation of Consecutive Binary Numbers LeetCode Solution with the best time and space complexity. The solution to Concatenation of Consecutive Binary Numbers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Concatenation of Consecutive Binary Numbers
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 <= 105
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(1)
1680. Concatenation of Consecutive Binary Numbers LeetCode Solution in C++
class Solution {
public:
int concatenatedBinary(int n) {
constexpr int kMod = 1'000'000'007;
long ans = 0;
for (int i = 1; i <= n; ++i)
ans = ((ans << numberOfBits(i)) % kMod + i) % kMod;
return ans;
}
private:
int numberOfBits(int n) {
return log2(n) + 1;
}
}; /* code provided by PROGIEZ */
1680. Concatenation of Consecutive Binary Numbers LeetCode Solution in Java
class Solution {
public int concatenatedBinary(int n) {
final int kMod = 1_000_000_007;
long ans = 0;
for (int i = 1; i <= n; ++i)
ans = ((ans << numberOfBits(i)) % kMod + i) % kMod;
return (int) ans;
}
private int numberOfBits(int n) {
return (int) (Math.log(n) / Math.log(2)) + 1;
}
} // code provided by PROGIEZ
1680. Concatenation of Consecutive Binary Numbers LeetCode Solution in Python
class Solution:
def concatenatedBinary(self, n: int) -> int:
kMod = 1_000_000_007
ans = 0
def numberOfBits(n: int) -> int:
return int(math.log2(n)) + 1
for i in range(1, n + 1):
ans = ((ans << numberOfBits(i)) + i) % kMod
return ans # code by PROGIEZ
