MiddleКодИногдаЕщё не отвечали
Умножение длинного десятичного числа (строки цифр) на одну цифру
Неотрицательное целое хранится строкой десятичных цифр, младший разряд в нулевом индексе. Умножьте его на месте на одну цифру n, где 1 <= n <= 9.
Требования:
- O(1) доп. памяти; буфер может вырасти на один разряд без реаллокации.
- O(длины) по времени; корректно переносите разряды.
void multiplyByDigit(std::string& num, int n) {
// ваш код здесь
}Допишите реализацию.
Идём с младшего разряда. На каждой позиции считаем product = digit * n + carry, записываем обратно product % 10, кладём carry = product / 10. После цикла, пока carry > 0, дописываем carry % 10 как новые старшие разряды. Хранение от младшего разряда даёт переносу течь вперёд.
- ✗Забыть дописать остаточный перенос после последнего разряда
- ✗Сваливаться к целому фиксированной ширины, переполняющемуся на длинных числах
- ✗Идти от старшего разряда, из-за чего переносу некуда течь
- →Как изменится алгоритм, если разряды — 32-битные лимбы вместо основания 10?
- →Почему хранение младшим разрядом вперёд упрощает перенос?
Оглавление
Задача
Умножьте длинное число (строка цифр, младший разряд первым) на цифру 1 <= n <= 9 на месте.
Решение
#include <string>
void multiplyByDigit(std::string& num, int n) {
int carry = 0;
for (char& ch : num) { // от младшего разряда
int product = (ch - '0') * n + carry;
ch = char('0' + product % 10);
carry = product / 10;
}
while (carry > 0) { // дописываем старшие разряды
num.push_back(char('0' + carry % 10));
carry /= 10;
}
}Ключевые моменты
product = цифра * n + carry; сохраняем% 10, переносим/ 10.- Остаточный перенос дописывается как новые старшие разряды.
- Никакого
long long: длинное число не помещается в фиксированный тип.
Оглавление
