Почему это работает
- В столбце складываются не больше трёх единиц: две цифры и перенос, поэтому sum равно 0, 1, 2 или 3, то есть 00, 01, 10 или 11. Младший бит, sum & 1, — цифра ответа, а бит над ним, sum >> 1, — перенос.
- Число, которое кончилось, просто прибавляет 0, поэтому длины a и b могут быть любыми, и короткое не нужно дополнять нулями.
- Цикл идёт и пока carry = 1: в нашем примере последний перенос становится старшей единицей, и ответ на цифру длиннее обоих чисел.
Сложность
Время O(n + m): один проход по цифрам a и b и самое большее ещё один столбец для последнего переноса. Память O(max(n, m)) на сам ответ; остальное — несколько чисел.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗