Java O(n),  straight forward,
\nclass Solution {\n    public int[] addNegabinary(int[] arr1, int[] arr2) {\n        int length1 = arr1.length;\n        int length2 = arr2.length;\n        in
```\nclass Solution {\n    public int[] addNegabinary(int[] arr1, int[] arr2) {\n        int length1 = arr1.length;\n        int length2 = arr2.length;\n        int length = Math.max(length1, length2);\n        int[] result = new int[length + 2];  // the result \n        for (int i = 0; i < length; i++) {\n            int forward = 0;\n            int i1 = length1 - i - 1;\n            int i2 = length2 -i - 1;\n            if (i1 >= 0) {\n                forward += arr1[i1];\n            }\n            if (i2 >= 0) {\n                forward += arr2[i2];\n            }\n            forward += result[length + 1 - i];\n            if (forward >= 0) {\n                int tmp = forward % 2;\n                result[length + 1 - i] = tmp;\n                result[length - i] = -(forward / 2);\n            } else { // if forward less than 0, update the futher position\n                result[length + 1 - i] = 1;\n                result[length - i] = 1;\n            }\n        }\n\t\t// edit the result \n        if (result[1] < 0) { \n            result[0] = 1;\n            result[1] = 1;\n            return result;\n        } else {\n            int index = 0;  //remove the zero postion\n            while (index < length + 2 && result[index] == 0) {\n                index++;\n            }\n            if (index >= length + 2) {\n                return new int[]{0};\n            }\n            return Arrays.copyOfRange(result, index, length + 2);\n        }\n    }\n}\n```
[]