Crude O(sqrt(N)) C++ DFS
For every combination of positive bits ((-2)^0, (-2)^2, ...), the value of the negative part can easily be found as the difference between the target and the va
For every combination of positive bits (`(-2)^0`, `(-2)^2`, ...), the value of the negative part can easily be found as the difference between the target and the value of the positive bits. Then, if the negative bits are at the right places (`(-2)^1`, `(-2)^3`, ...), a correct solution has been found.\n\nThe actual complexity is around `O(2 ^ ceil(logN / 2))`, which is close to sqrt(N). This would surely not work if N was up to 10^18 and I\'m not proud of this solution, so I will keep trying to find the proper solution. I\'m just sharing this in case anyone is interested.\n\n_Update: I finally managed to think of the proper O(logN) solution with bitwise operations and much shorter code. I\'m still leaving this here as an example of an alternative (albeit dumb) solution though._\n\n```c++\nclass Solution {\npublic:\n    bool dfs(string& s, int index, int valueToSet, long long target, long long value) {\n        if (valueToSet == 0) {\n            s[index] = \'0\';\n            value -= 1LL << (s.length() - index - 1);\n        }\n        if (value < target) {\n            // Overshoot\n        } else if (index + 2 < s.length()) {\n            // Continue brute force\n            for (int i = 0; i <= 1; i++) {\n                if (dfs(s, index + 2, i, target, value)) {\n                    return true;\n                }\n            }\n        } else {\n            // All positive bits have been set. If the negative bits do not coincide with the positive ones, this is the solution.\n            const int delta = value - target;\n            bool isValid = true;\n            for (int i = 0; i < s.length() && isValid; i += 2) {\n                isValid = (delta & (1LL << (s.length() - i - 1))) == 0;\n            }\n            if (isValid) {\n                for (int i = 1; i < s.length(); i += 2) {\n                    if ((delta & (1LL << (s.length() - i - 1)))) {\n                        s[i] = \'1\';\n                    }\n                }\n                return true;\n            }\n        }\n        s[index] = \'1\';\n        return false;\n    }\n    \n    string baseNeg2(long long target) {\n        if (target == 0) {\n            return "0";\n        }\n        \n        long long value = 1;\n        string s = "1";\n        while (value < target) {\n            value += 1LL << (s.length() + 1);\n            s += "01";\n        }\n        dfs(s, 0, 1, target, value);\n        return s;\n    }\n};\n```
[]