[Python 3] Bit manipulation, 4 solutions, 1 line, O(n), 44ms
Straightforward solution\n- Iteratively shift sum to the left by counter bit length and add the counter.\n- Iteratively get modulo 10\\9+7 to avoid slow big int
# Straightforward solution\n- Iteratively shift sum to the left by counter bit length and add the counter.\n- Iteratively get modulo 10\\*\\*9+7 to avoid slow big int operations.\n- Time complexity is O(n), space complexity is O(1).\n```\nclass Solution:\n    def concatenatedBinary(self, n: int) -> int:\n        s = 0\n        for i in range(1, n+1):\n            s = (s << i.bit_length() | i) % 1000000007\n            \n        return s\n```\n# Functional approach\nThe same algorithm in 1 line.\n```\nclass Solution:\n    def concatenatedBinary(self, n: int) -> int:\n        return reduce(lambda s, i: (s << i.bit_length() | i) % 1000000007, range(1, n+1))\n```\n# Lazy memoization\n- Since task for small ```n``` is a subtask for big ```n``` we can cache all ```n``` to avoid duplicated calculations.\n- Time complexity is O(n), space complexity is O(n).\n```\nclass Solution:\n    mem = [0]\n        \n    def concatenatedBinary(self, n: int) -> int:\n        for i in range(len(Solution.mem), n+1):\n            Solution.mem.append((Solution.mem[-1] << i.bit_length() | i) % 1000000007)\n        \n        return Solution.mem[n]\n```\n# Greedy memoization, 44ms\n- Since we know n <= 10\\*\\*5 we can precalculate all ```n```.\n- Time complexity is O(1) and initialization O(n), space complexity is O(n)\n```\nclass Solution:\n    mem = list(accumulate(range(100001), lambda s, i: (s << i.bit_length() | i) % 1000000007))\n        \n    def concatenatedBinary(self, n: int) -> int:\n        return Solution.mem[n]\n```\n\n
['Bit Manipulation', 'Memoization', 'Python']