Let Me Explain How The Negative Base Works
Imagine a normal base 2. the code would be\n\n...\nwhile (N != 0) {\n\tif (N % 2 == 0) sb.append(\'0\');\n\telse sb.append(\'1\');\n\tN /= 2;\n}\n...\n\neverybo
1. Imagine a normal base 2. the code would be\n```\n...\nwhile (N != 0) {\n\tif (N % 2 == 0) sb.append(\'0\');\n\telse sb.append(\'1\');\n\tN /= 2;\n}\n...\n```\neverybody happy happy. \n\n2. Why it\'s like that? It\'s because when we do N / 2, Java helps us get rid of the fraction part. Like N is odd, maybe 5, then 5 / 2 = 2, then remainder 1 is recorded as part of the bits. \nHint: The remainder is 1 because 5 = 2 * 2 + 1. happy until here?\n\n3. Well it doesn\'t work exactly the same with negative bases!\nImagine we have a negative base -2, N = -5, what happens then? Which one below do you think is the remainder formula?\na) -5 = (-2) * 2 + (-1)\nb) -5 = (-2) * 3 + 1\nGuess what? The remainder should always be positive! That means the remainder is 1, not -1. The multiple should be 3, not 2.\n\n4. Java always wants to get rid of the fraction (to flooring), so we will get -5 / -2 = 2. Well works good for positive bases. But for negative bases we need it to ceiling, not flooring. We need -5 / -2 = 3.\n\n5. There are multiple ways to achieve it. I choose to change the formula b) a little bit. \nb) -5 = (-2) * 3 + 1\nIf we subtract -5 by the remainder 1, then -6 / (-2) = 3, we get the 3 we needed. \n\n6. **IMPORTANT!! **The idea is to transfer the weird odd negative number to a even number. When it\'s even, we avoid Java divising numbers against the real Math. We get the ceiling we want.\n\n6. Now we happy happy again.\n\n\n```\nclass Solution {\n    public String baseNeg2(int N) {\n        if (N == 0) return "0";\n        \n        StringBuilder sb = new StringBuilder();\n        while (N != 0) {\n            if (N % -2 == 0) sb.append(\'0\');\n            else {\n                sb.append(\'1\');\n                N--;\n            }\n            N /= -2;\n        }\n        return sb.reverse().toString();\n    }\n}\n```
[]