Java  solution O(n) & 1ms
\nclass Solution {\n    public int[] addNegabinary(int[] arr1, int[] arr2) {\n        int len1 = arr1.length;\n        int len2 = arr2.length;\n\n        if (le
```\nclass Solution {\n    public int[] addNegabinary(int[] arr1, int[] arr2) {\n        int len1 = arr1.length;\n        int len2 = arr2.length;\n\n        if (len1 == 0) {\n            return arr2;\n        }\n        if (len2 == 0) {\n            return arr1;\n        }\n        int maxLen = (len1 > len2 ? len1 : len2) + 2;\n        int[] result = new int[maxLen];\n        int carry = 0;\n        int i = 0;\n\t\t// deal with the common part where both the arrays has numbers\n        while (len1 - 1 - i >= 0 && len2 - 1 - i >= 0) {\n            int sum = arr1[len1 - 1 - i] + arr2[len2 - 1 - i] + carry;\n            result[maxLen - 1 - i] = getBit(sum);\n            carry = getCarry(sum);\n            ++i;\n        }\n\t\t// deal with the rest part\n        while (len1 - 1 - i >= 0 && maxLen - 1 - i >= 0) {\n            int sum = arr1[len1 - 1 - i] + carry;\n            result[maxLen - 1 - i] = getBit(sum);\n            carry = getCarry(sum);\n            ++i;\n        }\n        while (len2 - 1 - i >= 0 && maxLen - 1 - i >= 0) {\n            int sum = arr2[len2 - 1 - i] + carry;\n            result[maxLen - 1 - i] = getBit(sum);\n            carry = getCarry(sum);\n            ++i;\n        }\n\t\t// deal with the remaining carry\n        while (maxLen - 1 - i >= 0 && carry != 0) {\n            result[maxLen - 1 - i] = getBit(carry);\n            carry = getCarry(carry);\n            ++i;\n        }\n\t\t\n\t\t// remove the lead zeros\n        int zeroLeadCount = 0;\n        while (zeroLeadCount < maxLen && result[zeroLeadCount] == 0) {\n            zeroLeadCount++;\n        }\n        if (zeroLeadCount == maxLen) {\n            return new int[] {0};\n        }\n        int[] res = new int[maxLen - zeroLeadCount];\n        for (int k = 0; k + zeroLeadCount < maxLen; k++) {\n            res[k] = result[k + zeroLeadCount];\n        }\n        return res;\n    }\n    \n\t// get carry according to the addition result number\n    private int getCarry(int num) {\n        if (num == 2 || num == 3) {\n            return -1;\n        }\n        if (num == -1) {\n            return 1;\n        }\n        return 0;\n    }\n\n    // get bit according to the addition result number\n    private int getBit(int num) {\n        if (num == 2) {\n            return 0;\n        }\n        if (num == 3 || num == -1 || num == 1) {\n            return 1;\n        }\n        return 0;\n    }\n}\n```
[]