C++ | Bit Manipulation Appraoch ✅
If you like it, please give a star, to my Github Repository and upvote this post.\n\nIntuition:\nThe answer is the sum of the binary representations of the numb
**If you like it, please give a star, to my [Github](https://github.com/champmaniac/LeetCode) Repository and upvote this post.**\n\n**Intuition:**\nThe answer is the **sum** of the binary representations of the numbers from `1 to n`. The binary representation of a number is the sum of the **powers** of `2` that make up the number. The powers of `2` are the same as the **binary** representation of the number.\n\n**Approach:**\n* Iterate through the numbers from `1 to n` and add the `binary` representation of `each` number to the `answer`.\n* `ans` `= ans<<`(`number of bits in the binary representation of the current number`) + `binary representation of the current number.`\n\n**C++:**\n```\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        int mod = 1e9 + 7;\n        long long ans = 0;\n        int len = 0;\n        for (int i = 1; i <= n; i++) {\n            if ((i & (i - 1)) == 0) {\n                len++;\n            }\n            ans = ((ans << len) + i) % mod;\n        }\n        return ans;\n    }\n};\n```\n****\n**Time Complexity:** **O(n)**, where `n`: input number\n**Space Complexity:** **O(1)**\n****\n\n
['Bit Manipulation', 'C', 'C++']