My Solutions
Solution I\n\n/**\n * Time Complexity: O(max(n1, n2))\n * Space Complexity: O(1)\n * where `n1` is the length of the vector `arr1`\n *       `n2` is the length 
**Solution I**\n```\n/**\n * Time Complexity: O(max(n1, n2))\n * Space Complexity: O(1)\n * where `n1` is the length of the vector `arr1`\n *       `n2` is the length of the vector `arr2`\n */\nclass Solution {\n public:\n  vector<int> addNegabinary(const vector<int> &arr1, const vector<int> &arr2) {\n    constexpr int binary = 2;\n    const int n1 = static_cast<int>(arr1.size());\n    const int n2 = static_cast<int>(arr2.size());\n    vector<int> ret;\n    for (int carry = 0, i = 0, i1 = n1 - 1, i2 = n2 - 1; i1 > -1 || i2 > -1 || carry != 0; ++i, --i1, --i2) {\n      const int coefficient = (i & 0b1) == 0b1 ? -1 : 1;\n      const int d1 = (i1 > -1 ? arr1[i1] : 0) * coefficient;\n      const int d2 = (i2 > -1 ? arr2[i2] : 0) * coefficient;\n      const int d = d1 + d2 + carry;\n      carry = d / binary;\n      ret.emplace_back(d & 1);\n      if ((d & 0b1) == 0b1 && d * coefficient < 0) {\n        carry += -1 * coefficient;\n      }\n    }\n    while (ret.size() > 1 && ret.back() == 0) {\n      ret.pop_back();\n    }\n    reverse(ret.begin(), ret.end());\n    return ret;\n  }\n};\n```\n**Solution II**\n```\n/**\n * Time Complexity: O(max(n1, n2))\n * Space Complexity: O(1)\n * where `n1` is the length of the vector `arr1`\n *       `n2` is the length of the vector `arr2`\n */\nclass Solution {\n public:\n  vector<int> addNegabinary(const vector<int> &arr1, const vector<int> &arr2) {\n    const int n1 = static_cast<int>(arr1.size());\n    const int n2 = static_cast<int>(arr2.size());\n    vector<int> ret;\n    for (int carry = 0, i1 = n1 - 1, i2 = n2 - 1; i1 > -1 || i2 > -1 || carry != 0; --i1, --i2) {\n      const int d1 = i1 > -1 ? arr1[i1] : 0;\n      const int d2 = i2 > -1 ? arr2[i2] : 0;\n      const int d = d1 + d2 + carry;\n      carry = -(d >> 1);\n      ret.emplace_back(d & 1);\n    }\n    while (ret.size() > 1 && ret.back() == 0) {\n      ret.pop_back();\n    }\n    reverse(ret.begin(), ret.end());\n    return ret;\n  }\n};\n```
[]