C++ (100%) with maths equations converting base 10 to base -2
I didnt really understand the explanation from any other posts so I decided to look up the maths and now this make sense... I will try explain it here.\n(hope i
I didnt really understand the explanation from any other posts so I decided to look up the maths and now this make sense... I will try explain it here.\n(hope i fixed all the typos..)\n\nImagine you have a base 10 number say 2, how do you write this in terms of 10s or in base 10? Its 0 x 10^1 + 2 x 10^0.\nSo the base 2 representation for 2 is: 1 x 2^1 + 0 x 2^0. You can generalise this representation with this formula:\n![image](https://assets.leetcode.com/users/images/ac05a260-5e96-4c90-b5bd-3c74b3c78bda_1633552420.684553.png) - Eq1\nwhere N is your base 10 number, q is base, x for base 10 numbers are from 0 to 9, x for base 2 numbers are 0 or 1. x can never be -ve because x represents how many base numbers there are. In the case of base 10 we had 0 x 10^1 + 2 x 10^0, this means there are 0 (10^1) and 2 (10^0).\nYou can expand this concept to for any base. Lets go through the example for base 2 first.\n\n**Step 1**:\nwe have:\n![image](https://assets.leetcode.com/users/images/f0d62ebd-cd1e-4631-99b1-89da99b90ea0_1633552943.29362.png) - Eq2\nOne observation we need to make is when N is even, we know that ![image](https://assets.leetcode.com/users/images/97f814b2-d75c-4b98-915f-7a7305387fc4_1633552883.7546272.png) will always be 0 and when N is odd, it will always be 1. So in this case there, we know it should be 0 so now we have:\n![image](https://assets.leetcode.com/users/images/30e41bfb-650a-410e-b3d1-1f2666175843_1633553018.4380875.png) - Eq3\nNow lets take a factor of base (2) our from Eq 3 we have:\n![image](https://assets.leetcode.com/users/images/b82ce02b-ffb9-4c0d-a383-078a50927b50_1633555531.5433874.png) - Eq4\n**Step 2**: \nWe know the formula inside the backet from Eq4 must equate one so we can then write:\n![image](https://assets.leetcode.com/users/images/a47044d6-88aa-456c-b148-786772188f30_1633553313.1689572.png) - Eq5\nN = 1 is odd, so the last term ![image](https://assets.leetcode.com/users/images/b67ac47f-6f21-4943-a6e3-22738148c070_1633553419.6779156.png) here must yield to 1:\n![image](https://assets.leetcode.com/users/images/becb3e44-6ac3-45a4-905c-b97cf74a967f_1633553383.5358896.png) - Eq6\nYou can see where this is going but for the sake of algo, we continue. Now take a factor of base (its 2) out again:\n![image](https://assets.leetcode.com/users/images/4a32f603-afc6-48a1-9601-60fcbfb43eeb_1633555380.5031097.png) - Eq7\nNow you can see the part inside the bracket must be 0 so now we stop.\n\nNow if you look back at the two steps in reverse, we had 1 and 0 as the remainders each time/step we devided by the base. So our base 2 representation of 2: "10".\n\nDo this for base of -2:\n**Step 1**:\nN = 2 so its even:\n![image](https://assets.leetcode.com/users/images/6d798112-6b2e-4436-abae-056a90c5d0b6_1633553867.8128097.png) - Eq8\nThe bracket inside the last equation must equate -1 so:\n**Step 2**:\n-1 is odd so:\n![image](https://assets.leetcode.com/users/images/6574d172-da50-46b5-841f-68f82974f072_1633554020.2229135.png) - Eq9\nAgain, bracket inside the last equation must equate 1 so:\n**Step 3**:\n![image](https://assets.leetcode.com/users/images/8b5066f4-7437-4d8c-bf91-8f21b8ba4c8b_1633557140.8774428.png) - Eq10\n And here we know the bracket inside the last line of equation in Eq10 is 0 so we stop!\n\nNow lets look at the remainders for each steps in reverse: "110" which is the answer!\n\nI recommend you to do the above yourself to understand each steps and then code.\n\nReply in comments if you have questions.\n\n```\nclass Solution \n{\npublic:\n    string baseNeg2(int n) \n    {\n        if (n == 0)\n        {\n            return string("0");\n        }\n        \n        string bin;\n        const int base = -2;\n        \n        while (n != 0)\n        {\n            int remainder = n % 2;\n            if (remainder == 0)\n            {\n                bin.push_back(\'0\');\n                n = n / base;\n            }\n            else\n            {\n                bin.push_back(\'1\');\n                n = (n - 1) / base;\n            }\n        }\n        \n        reverse(bin.begin(),bin.end());\n        \n        return bin;\n    }\n};\n```
[]