Ещё задача в Amazon

Даны две бинарные строки a и b, нужно их сложить))

Пример
a = "11", b = "1"
a + b = "100"

Длины строк от 1 до 10^5

Решение:
От такой задачи разрешается подпрыгнуть от радости на собеседовании, громко ударить кулаком об стол, закричать ОЧЕВ и отключиться от собеседования

По символьно считываем строки, складываем символы и поддерживаем добавляемое значение в следующий разряд. ВСЁ

string addBinary(string a, string b) {
if (a.size() > b.size())
swap(a, b);

int n = (int)a.size(), m = (int)b.size();
if (n < m) {
a = string(m - n, '0') + a;
n = m;
}

string res;
int pred = 0;
for (int i = n - 1; i >= -1; --i) {
if (i == -1 && pred == 0) break;

int d1 = 0, d2 = 0;
if (i > -1) {
d1 = a[i] - '0';
d2 = b[i] - '0';
}

if (d1 + d2 == 2) {
res += (pred ? "1" : "0");
pred = 1;
} else if (d1 + d2 == 1) {
res += (pred ? "0" : "1");
} else {
res += (pred ? "1" : "0");
pred = 0;
}
}

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

return res;
}

Решение за O(N)

@algoses