[C++] Linear Time, Constant Space Solution Explained, 100% Time, 100% Space
Great problem to tackle and, since it was pretty straightforward, I gave myself a few extra challenges:\n no conversion to string (that will not look cool to mo
Great problem to tackle and, since it was pretty straightforward, I gave myself a few extra challenges:\n* no conversion to string (that will not look cool to most interviewers anyway);\n* no sorting;\n* getting there with constant space.\n\nAnd it looks like I did it \uD83C\uDF8A !\n\nIn order to proceed, first of all I declared as a `static constexpr` a 2D array with all the powers of 2 up to the given limit (`9` digits), grouped by number of digits, so that I could have a smoother lookup later.\n\nIn the main function, we will declare 2 support variables:\n* `digits` is an array of `9` elements (again, the maximum we might have to consider;\n* `pos` is a pointer that will tell us where to write or up to where to read in `digits`, preset to `0`.\n\nWe will then proceed to destructure `n` into its base digits, proceeding until it is reduced to `0` and:\n* assign its quotient and remainder to the aptly named `qr`;\n* store the remainder in `digits`, while also increasing `pos` by `1`;\n* update `n` to be the quotient - ie: functionally shaving off the least significant/leftmost digit that we just store.\n\nOnce done, we will call `verifyDigits` with all the non-`0` values that we have in `powers[pos]` (ie: all the powers of 2 we pre-stored), returning `true` if anyone of them matches the content of digits (ie: the initial number was an "anagram" of any power of 2 with the same amount of digits).\n\n`verifyDigits` takes 3 parameters (our array/pointer `digits`, `pos` which doubles now as the size of `digits` and `n`, the pre-stored power of 2 to verify) and:\n* declare a support variable `check` as an array of `10` elements, all preset to `0`;\n* increase each matching cell of `check` by `1` for each element in `digits` up to `pos` - so, for example, if we had `digits = {3, 5, 6, 6, 5}`, `check` would be `{0, 0, 0, 1, 0, 2, 2, 0, 0, 0}`;\n* proceed to destructure `n` in a similar fashion to what we did before and:\n\t* put quotient and remainder into `qr`;\n\t* return `false` if any cell of `check` matching the remainder (ie: the least significant digits) ends up being reduced below `0`;\n\t* update `n` to be the quotient, shaving off again the least significant digit and moving on;\n* return `true` if we reach the end of the loop, since we successfully reduced `pos` elements in `check` without any of them going below `0`, which implies a perfect match!\n\nIf we are back in the main function, we will then return `false` at this point, since all the `digits` from the original `n` could not be used to make any known power of 2.\n\nThe code:\n\n```cpp\n// precomputed values of powers, grouped by number of digits\nstatic constexpr int powers[10][4] = {{}, {1, 2, 4, 8}, {16, 32, 64}, {128, 256, 512}, {1024, 2048, 4096, 8192}, {16384, 32768, 65536}, {131072, 262144, 524288}, {1048576, 2097152, 4194304, 8388608}, {16777216, 33554432, 67108864}, {134217728, 268435456, 536870912}};\n\nclass Solution {\n    bool verifyDigits(int *digits, int pos, int n) {\n        // support variables\n        int check[10] = {};\n        // preparing check\n        for (int i = 0; i < pos; i++) check[digits[i]]++;\n        // destructuring n into its digits\n        while (n) {\n            auto qr = div(n, 10);\n            // verifying if the matching least significant digit can be used\n            if (--check[qr.rem] < 0) return false;\n            // updating n\n            n = qr.quot;\n        }\n        return true;\n    }\npublic:\n    bool reorderedPowerOf2(int n) {\n        // support variables\n        int digits[9], pos = 0;\n        // destructuring n into its digits\n        while (n) {\n            auto qr = div(n, 10);\n            // storing the least significant digit of n\n            digits[pos++] = qr.rem;\n            // updating n\n            n = qr.quot;\n        }\n        // checking if we have a match for any known power of 2 with the same amount of digits\n        for (int n: powers[pos]) if (n && verifyDigits(digits, pos, n)) return true;\n        return false;\n    }\n};\n```
['C', 'C++']