Short Java Solution O(n) beats 100% no stack
\nclass Solution {\n    public int[] addNegabinary(int[] arr1, int[] arr2) {\n        if(arr1.length < arr2.length) return addNegabinary(arr2, arr1); \n        
```\nclass Solution {\n    public int[] addNegabinary(int[] arr1, int[] arr2) {\n        if(arr1.length < arr2.length) return addNegabinary(arr2, arr1); \n        int sho = arr2.length;\n        int lo = arr1.length;\n        int carry = 0; \n        List<Integer> arr = new ArrayList<>(); \n        for(int i = 1; i<=lo; i++){\n            int num = 0; \n            num = arr1[arr1.length-i] + ((i <= sho)? arr2[arr2.length-i] : 0) + carry;  \n            if(num == 2){\n                arr.add(0,0);\n                carry = -1; \n            }else if(num == -1){\n                arr.add(0, 1); \n                carry = 1; \n            }else if(num ==3){\n                arr.add(0,1);\n                carry = -1; \n            }else{\n                arr.add(0, num%2);\n                carry = num/2;\n            }\n        }\n        if(carry !=0){\n                arr.add(0,1);\n                arr.add(0,1);\n        }\n        while(arr.get(0) == 0 && arr.size() >1) arr.remove(0); \n        int[] rst = new int[arr.size()];\n        for(int i = 0; i< arr.size(); i++){\n            rst[i] = arr.get(i);\n        }\n        return rst; \n    }   \n}\n```
[]