[C++] from TLE to 40ms.
inituitive brute force. We add each number bit by bit. But this will be TLE.\n\nclass Solution {\n public:\n  int concatenatedBinary(int n) {\n    int ans = 0;\
inituitive brute force. We add each number bit by bit. But this will be TLE.\n```\nclass Solution {\n public:\n  int concatenatedBinary(int n) {\n    int ans = 0;\n\t\n\tstack<int> stk;\n\n    for (int i = 1; i <= n; ++i) {\n      int x = i;\n\n      while (x > 0) {\n        stk.push(x % 2);\n        x /= 2;\n      }\n\n      while (!stk.empty()) {\n        ans = ans * 2 + stk.top();\n        stk.pop();\n\n        ans %= 1000000007;\n      }\n    }\n\n    return ans;\n  }\n};\n```\n\nWe can optimize the following part to reduce the cost.\n```\n      while (!stk.empty()) {\n        ans = ans * 2 + stk.top();\n        stk.pop();\n\n        ans %= 1000000007;\n      }\n```\nupdate it to\n```\nans = (ans << len) % mod + i;\n```\n\nWhat happend here is with the second solution we add the whole number with one ```<<``` operation instead of multiple ```<<``` operations with the first solution.\n```len``` is the binary length of a number which is equal to stack length of the first solution.\nIn another words, we recude ```<<``` operator from ```len``` times to 1 time.\n\nSolution 2,\n```\nclass Solution {\n public:\n  int concatenatedBinary(int n) {\n    long ans = 0;\n    const int mod = 1000000007;\n\n    for (int i = 1; i <= n; ++i) {\n      int x = i, len = 0;\n\n      while (x > 0) {\n        ++len;\n        x /= 2;\n      }\n\n      ans = (ans << len) % mod + i;\n    }\n\n    return ans % mod;\n  }\n};\n```\n\nThanks to @jitendragupta1981,  we could make it more reasonable.\n```\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        long ans = 0;\n        const int mod = 1000000007;\n        \n        for (int i = 1; i <= n; ++i) {\n            int x = i, len = 0;\n            \n            while (x > 0) {\n                ++len;\n                x /= 2;\n            }\n            \n            ans = ((ans << len) + i) % mod; // or ans = ((ans << len) | i) % mod;\n        }\n        \n        return ans % mod;\n    }\n};\n```
[]