Adding Two Negabinary Numbers LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> addNegabinary(vector<int> &arr1, vector<int> &arr2) {
4
    int i = arr1.size() - 1;
5
    int j = arr2.size() - 1;
6

7
    // prestore bits and carry for different sum values
8
    vector<int> bits = {0, 1, 0, 1, 0, 1};
9
    vector<int> carries = {1, 1, 0, 0, -1, -1};
10

11
    vector<int> res;
12

13
    int sum;
14
    int carry = 0;
15

16
    // perform binary addition using sum and prestored bit and carry values
17
    while (i >= 0 || j >= 0 || carry) {
18
      sum = carry + (i >= 0 ? arr1[i--] : 0) + (j >= 0 ? arr2[j--] : 0);
19

20
      carry = carries[sum + 2];
21

22
      res.push_back(bits[sum + 2]);
23
    }
24

25
    // remove leading zeroes
26
    while (res.size() > 1 && res.back() == 0) res.pop_back();
27

28
    reverse(res.begin(), res.end());
29

30
    return res;
31
  }
32
};