ee
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n\n    // positive base => max(n1,n2) <= len of sum <= max(n1,n2) + 1\n    // negative base => 0 <= len of sum <= max(n1,n2) + 2\n    // can be subtraction so any len up to (max(n1,n2) + 2)\n    // because the real number might need (max(n1,n2) + 1) but because of negative powers\n    // we might have to use 1 more bit to skip the negative power at the front\n\n\n    //  -2^1  -2^0\n    // [1,1,1,1,1]  = 11\n    //     [1,0,1]  = 5\n    // [1,0,0,0,0]  = 16\n    // [4,3,2,1,0] powers\n\n    // [1,1,1,1,1]  = 11\n    //     [1,0,1]  = 5\n    // [1,0,0,0,0]  = 16\n\n    //     [1] = 1\n    //     [1] = 1\n    // [1,1,0] = 2\n    public int[] addNegabinary(int[] A1, int[] A2) {\n        int n1 = A1.length;\n        int n2 = A2.length;\n        int biggerN = Math.max(n1, n2);\n        int maxLen = biggerN + 2;\n        ArrayList<Integer> reversed = new ArrayList<>(maxLen);\n\n        int carry = 0;\n        int base = -2;\n        int loopsRemaining = maxLen;\n        int i = 1; // how much to subtract from N, to get id\n        while (loopsRemaining-- > 0) {\n            int a = n1 - i < 0 ? 0 : A1[n1 - i];\n            int b = n2 - i < 0 ? 0 : A2[n2 - i];\n            int sum = a + b + carry;\n            int r = sum % base; // bits we put here = residual of current power\n            carry = sum / base; // carryover bits;  carry over main part for higher power\n\n            if (r < 0) {\n                r += Math.abs(base);// r < 0 !! handle!!!\n                carry++;\n            }\n            reversed.add(r);\n            i++;\n        }\n\n        int j = reversed.size() - 1;\n        while (j > 0 && reversed.get(j) == 0) j--;\n\n        int k = 0;\n        int[] ans = new int[j + 1];\n        while (j >= 0) ans[k++] = reversed.get(j--);\n        return ans;\n    }\n\n\n}\n```
['Java']