1680. Concatenation of Consecutive Binary Numbers

Question Given an integer n, returns the decimal value of the binary string formed by concatenating the binary representations 1 through n in order, modulo 109 + 7. Example 1: Input: n = 1 Output: 1 Explanation: "1" in binary format corresponds to a decimal value of 1. Example 2: Input: n = 3 Output: 27 Explanation: In binary, 1, 2 and 3 correspond to "1", "10" and "11". After concatenating them, we have "11011", which corresponds to the decimal value of 27. Example 3: Input: n = 12 Output: 505379714 Explanation: The result of the concatenation is "1101110010111011110001001101010111100". The decimal value is 118505380540. After modulo 109 + 7, the result is 505379714. Solution class Solution { public: int concatenatedBinary(int n) { long ans = 0, mod = 1e9+7, length = 0; for (int i = 1; i <= n; ++i) { if ((i & (i - 1)) == 0) length++; ans = ((ans << length) + i) % mod; } return ans; } };