🔥 [LeetCode The Hard Way] 🔥 Explained Line By Line
Please check out 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 li
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```
['Bit Manipulation', 'C', 'Python', 'C++', 'Java', 'Go', 'Python3']