Задача с таким, на первый взгляд, простым условием встречается на собеседовании в одной известной компании:
Даны два целых неотрицательных числа. Они слишком большие для представления в виде стандартных числовых типов, выходят за пределы int64. Числа даны в виде двух слайсов. Требуется вывести результат их сложения.
Решение
Складывать будем столбиком, как в начальных классах на уроках математики.
Для простоты возьмем слайсы небольшой длины, так как общий алгоритм подойдет для любых входных значений.
1. Определяем длину наибольшего слайса.
2. Инициализируем новый слайс для результата. Из-за возможного переноса при сложении старших разрядов результат может быть на одну цифру длиннее наибольшего из слагаемых. Поэтому к длине из 1 шага добавляем единицу.
3. Устанавливаем переменную carry (перенос) в 0. Она будет использоваться для хранения переноса из предыдущего разряда в следующий.
4. Итерируемся по каждому разряду чисел, начиная с младших и двигаемся к старшим. Если один из слайсов короче, используем 0 в качестве его цифры на соответствующем месте.
5. Складываем соответствующие цифры двух чисел и добавляем перенос carry.
6. Делим полученную сумму на 10. Целая часть будет новым значением carry, а остаток от деления, записываем в текущий разряд результата.
7. Если после завершения цикла carry равен нулю - отсутствует перенос в новый старший разряд - удаляем этот разряд из результата.
8. В обратном случае, первый элемент результирующего слайса устанавливается равным carry.
