Python, O(n), O((log n)^2) Follow-up, with Explanation
O(n) Solution\n### Idea\nGo from 1 to n. For each i, shift the answer left for the length of the binary of i, plus i and mod p=10**9+7.\n\nOptimizations include
## **O(n) Solution**\n### Idea\nGo from 1 to `n`. For each `i`, shift the answer left for the length of the binary of `i`, plus `i` and mod `p=10**9+7`.\n\nOptimizations include: \n1) Maintain the length of current `i` with `cur_ibit` and use `next_bit` to detect when to increase. I bet this would be faster than calling `int.bit_length()` on every `i`.\n2) Use `ans |= i` instead of `ans += i` as the last bits that fit `i` will always be zeros.\n\n```python\nclass Solution:\n    def concatenatedBinary(self, n: int, p: int = 10 ** 9 + 7) -> int:\n        ans = 0\n        next_bit = 1\n        cur_ibit = 0\n        for i in range(1, n+1):\n            if i >= next_bit:\n                next_bit <<= 1\n                cur_ibit += 1\n            ans <<= cur_ibit\n            ans |= i\n            ans %= p\n        return ans\n```\n\n#### Complexity\n- O(n) time. Going over through `1..n`. \n- O(1) space. Only a few extra variables.\n\n#### Submission stats\nRuntime: 972 ms (beats 94.60 %)\nMemory Usage: 14.1 MB (beats 84.51 %)\n\n## **O((log n)^2) Solution**\nWe can achieve better time complexity with some math -- more specifically, matrix multiplication. \n \n #### Idea\n When processing with `i`, the accumulation of `ans` goes as `ans = (ans << i.bit_length()) + i`. If we use a vector of `v[i] = [ans[i], i+1, 1]`, we can write this process as matrix operation `v[i+1] = M_B @ v[i]`: \n![image](https://assets.leetcode.com/users/images/6c747977-4e3a-41f7-8eb5-b5ea77450547_1611760024.7572007.png),\nwhere `B = 1 << i.bit_length()` and it is the same for all `2^k <= i < 2^(k+1)`.\n\nThe good thing now is that we can fast compute the accumulative effect of those `2^k <= i < 2^(k+1)` (`2^k` of them) that share the same `B` using matrix power ![image](https://assets.leetcode.com/users/images/c220dfd3-54a4-4336-a7d2-f70a3ad71238_1611760413.3877525.png), which takes O(k) time (see `matpowv()`).\n\nNow for a given `n`. Say `n = 25`. We start with `v[0] = [0, 1, 1]`. Then we do this matrix power thing for `i` in `[1, 2)`, `[2, 4)`, `[4, 8)`, `[8, 16)`, `[16, 26)`. That is, we calculate ![image](https://assets.leetcode.com/users/images/ab09df56-2b5c-4495-bb37-0a0bac920f29_1611760793.1534994.png) for `B, k = 2, 0`; `4, 1`; `8, 2`; `16, 3`; `32, 4`. In code, we do not explicitly keep `k` but instead use `min(bit, n - bit)` to get the power term. The final answer is `v[25][0]`.\n\nOptimizations:\n1) Same as before, use `bit` to keep track of the most significant bit instead of calculate it every time.\n2) Collapse matrices into the vector (`matpowv()`) every time to reduce the number of multiplication and additions from 3^3 (matrix multiplies matrix, `matmul()`) to 3^2 (matrix multiplies vector, `mv()`).\n\n\n```python\ndef matmul(X, Y, p):\n    return [[sum(a * b for a, b in zip(X_row, Y_col)) % p for Y_col in zip(*Y)] for X_row in X]\n\ndef mv(X, v, p):\n    return [sum(a * b for a, b in zip(X_row, v)) % p for X_row in X]\n\ndef matpowv(X, n, v, p):\n    while n > 0:\n        if n & 1: v = mv(X, v, p)\n        X, n = matmul(X, X, p), n >> 1\n    return v\n\nclass Solution:\n    def concatenatedBinary(self, n: int, p: int = 10 ** 9 + 7) -> int:\n        n += 1\n        v = [0, 1, 1]\n        bit = 1\n        while bit < n:\n            M = bit << 1\n            mat = [\n                [M, 1, 0],\n                [0, 1, 1],\n                [0, 0, 1],\n            ]\n            npow = min(bit, n - bit)\n            v = matpowv(mat, npow, v, p)\n            bit = M\n        return v[0]\n```\n\n### Complexity\n- O((log n)^2) time. O(log n) for going up bit by bit from 1 to n. For each bit, O(log bit) ~ O(log n) for calculating the matrix pow. The size of matrices are irrelavent of n and are always 3x3 and thus the time complexity for matmul is O(1).\n- O(1) space. The matrices involved take up O(1) space (irrelavent of n). \n\n### Submission stats\nRuntime: 292 ms (beats 97.66 %)\nMemory Usage: 14.3 MB (beats 53.67 %)\n\n---\nIf you find this helpful, please **upvote**! Thank you!!! :-)\n\nAcknowledgement: The idea of the matrix solution comes from [@rbx](https://leetcode.com/rbx)\'s [post](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/discuss/963549/python-(log(n))-2-approach).
['Math', 'Bit Manipulation']