[C++] 4 Solutions Compared and Explained, ~80% Time, ~100% Space
So, for the first one I wanted to give me the extra challenge of not using long (more on that later) and so I decided to count from 1 to n, get the bits right a
So, for the first one I wanted to give me the extra challenge of not using `long` (more on that later) and so I decided to count from `1` to `n`, get the bits right and religiously add one bit at a time.\n\nTo do so I declared a sole support variable `res` in the main scope of the function, and a few more in our main loop:\n* `i` will be our main pointer, going from `1` to `n`, as mentioned;\n* `j` will take the value of `i` and copy it, just to be disassembled, bit by bit;\n* `bits` is going to be our storage for the bits of each number initially stored in `j` - given the maximum input size, we are fine with just `17` bits;\n* `pos` is the pointer we will use to work on `bits`, initially set to `0` (first cell).\n\nNow, in our main loop we will:\n* assign the value of `i` to `j`, as mentioned;\n* extract all the bits and store them in `bits`, with the added convenience of storing them in reverse order;\n* we will then reverse all the bits in `bits` into `res`, resetting `pos` to `0` again and at each step updating `res` to be double its previous value modulo `1000000007`, plus the current bit.\n\nOnce done, we can return `res` :)\n\nThe code, running at around 30% time, with significantly low memory consumption (arrays, what would we do without them?):\n\n```cpp\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        // support variables\n        int res = 0;\n        for (int i = 1, j, bits[17], pos = 0; i <= n; i++) {\n            j = i;\n            // extracting the bits\n            while (j) {\n                bits[pos++] = j % 2;\n                j >>= 1;\n            }\n            // applying the bits\n            while (pos) {\n                res = (res * 2) % 1000000007 + bits[--pos];\n            }\n        }\n        return res;\n    }\n};\n```\n\nNow, can we do better?\n\nBut of course, starting with removing the modulo operation, which is notoriously rather expensive, and changing the solution to this (bumped up to 40%):\n\n```cpp\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        // support variables\n        int res = 0;\n        for (int i = 1, j, bits[17], pos = 0; i <= n; i++) {\n            j = i;\n            // extracting the bits\n            while (j) {\n                bits[pos++] = j % 2;\n                j >>= 1;\n            }\n            // applying the bits\n            while (pos) {\n                res <<= 1;\n                res = (res > 1000000007 ? res - 1000000007 : res) + bits[--pos];\n            }\n        }\n        return res;\n    }\n};\n```\n\nCan we do even better? Sure.\n\nI admit I did not want to go there not to add extra complexity, but we really do not need to store the bit in `bits` if we "read" them from the left, so here is some further optimisation\n\nTo do so, we will add an extra support variable, `hasSeenBit`, and in our main loop we will change things a bit and have `j` be our binary pointer (is that even a term? Well, let\'s pretend it is), being initialised to `1 << bitLmt`, with `bitLmt` expressing the maximum amount of bits we will ever need - for example for `n == 20`, `bitLmt` will be set to `5` (`20` is `10100` in binary representation).\n\nWe will, in each loop:\n* reset `j` to be `1 << bitLmt` and `hasSeenBit` to be `false`;\n* we will then extract each bit with `bool(i & j)`, which in our previous example will give us `1`, `0`, `1`, `0` and `0`, as expected;\n* update `hasSeenBit`, so that it will be and stay `true` as soon as the first bit is found;\n* once a bit has been found, update `res` with the logic discussed above.\n\nThe code, which bumped with this change alone to almost 60%:\n\n```cpp\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        // support variables\n        int res = 0;\n        bool hasSeenBit;\n        for (int i = 1, j, bit, bitLmt = ceil(log2(n)); i <= n; i++) {\n            // preparing for a new loop\n            j = 1 << 17;\n            hasSeenBit = false;\n            // extracting the bits\n            while (j) {\n                // getting the next bit, from the left\n                bit = bool(i & j);\n                // updating hasSeenBit\n                hasSeenBit |= bit;\n                // updating res, only after we have found at least a bit\n                if (hasSeenBit) {\n                    res <<= 1;\n                    res = (res > 1000000007 ? res - 1000000007 : res) + bit;\n                }\n                j >>= 1;\n            }\n        }\n        return res;\n    }\n};\n```\n\nAnd finally the last "cheap" one - computing the length in bits of each number, shifting `res` (a `long`, not to risk overflows) by that amount and applying the same logic with modulo and, this time, the whole number in one go.\n\nThe last part in particular - not having to split the number into single bits, had the time jump over 80%:\n\n```cpp\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        // support variables\n        long res = 0;\n        for (int i = 1, j, bitLen; i <= n; i++) {\n            j = i;\n            bitLen = 0;\n            // computing the length in bits of i\n            while (j) {\n                bitLen++;\n                j >>= 1;\n            }\n            // shifting res by bitLen bits\n            res = (res << bitLen) % 1000000007 + i;\n        }\n        return res;\n    }\n};\n```
['Bit Manipulation', 'C', 'C++']