C++ solution / easy to understand
Given a number N, we have to check their representation in base -2.\nObservation\n Given a representation 1000101 = (1+ (-2^2)+(-2^6)) check the least significa
Given a number N, we have to check their representation in base -2.\nObservation\n* Given a representation 1000101 = (1+ (-2^2)+(-2^6)) check the least significant bit (if the bit is **on** then number is **odd** else the number is **even**)\n* We can get their representation in backward way. If the number N is odd now, we substract 1 and divided the number by -2 else we only divide the number by -2, finally we will repeat the same operation\n* Complexity time O(log(N))  \n\n**C++**\n<code>\n\n\tclass Solution {\n\tpublic:\n\t\tstring baseNeg2(int N) {\n\t\t\tif(N==0)return "0";\n        \n\t\t\tstring s="";        \n\t\t\twhile(N!=0){\n\t\t\t\tif(N%2==0){\n\t\t\t\t\ts+="0";\n\t\t\t\t}else{\n\t\t\t\t\ts+="1";\n\t\t\t\t\tN--;\n\t\t\t\t}\n\t\t\t\tN/=-2;\n\t\t\t}\n        \n\t\t\treverse(s.begin(),s.end());\n\t\t\treturn s;\n\t\t}\n\t};\n</code>\n\n**Recursive solution**\n<code>\n\n\tclass Solution {\n\tpublic:\n\t\tstring f(int N){\n\t\t\tif(N==0)return "";\n\t\t\tif(N%2==0)return f(N/-2)+"0";\n\t\t\treturn f((N-1)/-2)+"1";\n\t\t}\n\t\t\n\t\tstring baseNeg2(int N) {\n\t\t\tif(N==0)return "0";\n\t\t\treturn f(N);\n\t\t}\n\t};\n</code>
[]