Please check out [LeetCode The Hard Way](https://wingkwong.github.io/leetcode-the-hard-way/) for more solution explanations and tutorials. \nI\'ll explain my solution line by line daily and you can find the full list in my [Discord](https://discord.gg/Nqm4jJcyBf).\nIf you like it, please give a star, watch my [Github Repository](https://github.com/wingkwong/leetcode-the-hard-way) and upvote this post.\n\n---\n\n**Approach 1: Bit Manipulation**\n\n**C++**\n\n```cpp\n// Time Complexity: O(N)\n// Space Complexity: O(1)\nclass Solution {\npublic:\n // the idea is to use bit manipulation to set the current number based on the previous number\n // for example, \n // n = 1, ans = 0b1\n // n = 2 (10), we need to shift 2 bits of the previous ans to the left and add `n`\n // i.e. 1 -> 100 (shift 2 bits to the left) -> 110 (set `10`). ans = 0b110\n // n = 3 (11), we need to shift 2 bits of the previous ans to the left and add `n` \n // i.e 110 -> 11000 (shift 2 bits to the left) -> 11011 (set `11`). ans = 0b11011\n // n = 4 (100), we need to shift 3 bits of the previous ans to the left and add `n`\n // i.e. 11011 -> 11011000 (shift 3 bits to the left) -> 11011100 (set `100). ans = 0b11011100\n // so now we can see a pattern here\n // we need to shift `l` bits of the previous ans to the left and add the current `i` \n // how to know `l`? it is not difficult to see `x` only increases when we meet power of 2\n int concatenatedBinary(int n) {\n // `l` is the bit length to be shifted\n int M = 1e9 + 7, l = 0;\n // use long here as it potentially could overflow for int\n long ans = 0;\n for (int i = 1; i <= n; i++) {\n // i & (i - 1) means removing the rightmost set bit\n // e.g. 100100 -> 100000\n // 000001 -> 000000\n // 000000 -> 000000\n // after removal, if it is 0, then it means it is power of 2\n // as all power of 2 only contains 1 set bit\n // if it is power of 2, we increase the bit length `l`\n if ((i & (i - 1)) == 0) l += 1;\n // (ans << l) means shifting the orginal answer `l` bits to th left\n // (x | i) means using OR operation to set the bit\n // e.g. 0001 << 3 = 0001000\n // e.g. 0001000 | 0001111 = 0001111\n ans = ((ans << l) | i) % M;\n }\n return ans;\n }\n};\n```\n\n**Java**\n\n```java\n// Time Complexity: O(N)\n// Space Complexity: O(1)\nclass Solution {\n // the idea is to use bit manipulation to set the current number based on the previous number\n // for example, \n // n = 1, ans = 0b1\n // n = 2 (10), we need to shift 2 bits of the previous ans to the left and add `n`\n // i.e. 1 -> 100 (shift 2 bits to the left) -> 110 (set `10`). ans = 0b110\n // n = 3 (11), we need to shift 2 bits of the previous ans to the left and add `n` \n // i.e 110 -> 11000 (shift 2 bits to the left) -> 11011 (set `11`). ans = 0b11011\n // n = 4 (100), we need to shift 3 bits of the previous ans to the left and add `n`\n // i.e. 11011 -> 11011000 (shift 3 bits to the left) -> 11011100 (set `100). ans = 0b11011100\n // so now we can see a pattern here\n // we need to shift `l` bits of the previous ans to the left and add the current `i` \n // how to know `l`? it is not difficult to see `x` only increases when we meet power of 2\n public int concatenatedBinary(int n) {\n // `l` is the bit length to be shifted\n int M = 1000000007, l = 0;\n // use long here as it potentially could overflow for int\n long ans = 0;\n for (int i = 1; i <= n; i++) {\n // i & (i - 1) means removing the rightmost set bit\n // e.g. 100100 -> 100000\n // 000001 -> 000000\n // 000000 -> 000000\n // after removal, if it is 0, then it means it is power of 2\n // as all power of 2 only contains 1 set bit\n // if it is power of 2, we increase the bit length `l`\n if ((i & (i - 1)) == 0) l += 1;\n // (ans << l) means shifting the orginal answer `l` bits to th left\n // (x | i) means using OR operation to set the bit\n // e.g. 0001 << 3 = 0001000\n // e.g. 0001000 | 0001111 = 0001111\n ans = ((ans << l) | i) % M;\n }\n return (int) ans;\n }\n}\n```\n\n**Python**\n\n```py\n# Time Complexity: O(N)\n# Space Complexity: O(1)\nclass Solution:\n # the idea is to use bit manipulation to set the current number based on the previous number\n # for example, \n # n = 1, ans = 0b1\n # n = 2 (10), we need to shift 2 bits of the previous ans to the left and add `n`\n # i.e. 1 -> 100 (shift 2 bits to the left) -> 110 (set `10`). ans = 0b110\n # n = 3 (11), we need to shift 2 bits of the previous ans to the left and add `n` \n # i.e 110 -> 11000 (shift 2 bits to the left) -> 11011 (set `11`). ans = 0b11011\n # n = 4 (100), we need to shift 3 bits of the previous ans to the left and add `n`\n # i.e. 11011 -> 11011000 (shift 3 bits to the left) -> 11011100 (set `100). ans = 0b11011100\n # so now we can see a pattern here\n # we need to shift `l` bits of the previous ans to the left and add the current `i` \n # how to know `l`? it is not difficult to see `x` only increases when we meet power of 2\n def concatenatedBinary(self, n: int) -> int:\n M = 10 ** 9 + 7\n # `l` is the bit length to be shifted\n l, ans = 0, 0\n for i in range(1, n + 1):\n # i & (i - 1) means removing the rightmost set bit\n # e.g. 100100 -> 100000\n # 000001 -> 000000\n # 000000 -> 000000\n # after removal, if it is 0, then it means it is power of 2\n # as all power of 2 only contains 1 set bit\n # if it is power of 2, we increase the bit length `l`\n if i & (i - 1) == 0:\n l += 1\n # (ans << l) means shifting the orginal answer `l` bits to th left\n # (x | i) means using OR operation to set the bit\n # e.g. 0001 << 3 = 0001000\n # e.g. 0001000 | 0001111 = 0001111\n ans = ((ans << l) | i) % M\n return ans\n```\n\n**Go**\n\n```go\n// Time Complexity: O(N)\n// Space Complexity: O(1)\n\n// the idea is to use bit manipulation to set the current number based on the previous number\n// for example, \n// n = 1, ans = 0b1\n// n = 2 (10), we need to shift 2 bits of the previous ans to the left and add `n`\n// i.e. 1 -> 100 (shift 2 bits to the left) -> 110 (set `10`). ans = 0b110\n// n = 3 (11), we need to shift 2 bits of the previous ans to the left and add `n` \n// i.e 110 -> 11000 (shift 2 bits to the left) -> 11011 (set `11`). ans = 0b11011\n// n = 4 (100), we need to shift 3 bits of the previous ans to the left and add `n`\n// i.e. 11011 -> 11011000 (shift 3 bits to the left) -> 11011100 (set `100). ans = 0b11011100\n// so now we can see a pattern here\n// we need to shift `l` bits of the previous ans to the left and add the current `i` \n// how to know `l`? it is not difficult to see `x` only increases when we meet power of 2\nfunc concatenatedBinary(n int) int {\n // `l` is the bit length to be shifted\n ans, l, M := 0, 0, 1_000_000_007\n for i := 1; i <= n; i++ {\n // i & (i - 1) means removing the rightmost set bit\n // e.g. 100100 -> 100000\n // 000001 -> 000000\n // 000000 -> 000000\n // after removal, if it is 0, then it means it is power of 2\n // as all power of 2 only contains 1 set bit\n // if it is power of 2, we increase the bit length `l`\n if (i & (i - 1) == 0) {\n l += 1\n }\n // (ans << l) means shifting the orginal answer `l` bits to th left\n // (x | i) means using OR operation to set the bit\n // e.g. 0001 << 3 = 0001000\n // e.g. 0001000 | 0001111 = 0001111\n ans = ((ans << l) | i) % M\n } \n return ans\n}\n```

Concatenation of Consecutive Binary Numbers

Problem Description

Problem Description

Answer Panel