MiddleCodeOccasionalNot answered yet
Multiply a big decimal number (digit string) by a single digit
A non-negative integer is stored as a string of decimal digits, least-significant digit first. Multiply it in place by a single digit n with 1 <= n <= 9.
Requirements:
- O(1) extra memory; the buffer may grow by one digit without reallocating.
- O(length) time; propagate carries correctly.
void multiplyByDigit(std::string& num, int n) {
// your code here
}Write the implementation.
Walk from the least-significant digit. At each position compute product = digit * n + carry, store product % 10 back, set carry = product / 10. After the loop, while carry > 0 append carry % 10 as new high digits. Little-endian storage lets the carry flow forward naturally.
- ✗Forgetting to append the leftover carry after the last digit
- ✗Falling back to a fixed-width integer, which overflows for long numbers
- ✗Iterating most-significant-first so the carry has nowhere to flow
- →How does the algorithm change if digits are 32-bit limbs instead of base 10?
- →Why does least-significant-first storage simplify carry propagation?
Contents
Task
Multiply a big number (digit string, least-significant first) by a digit 1 <= n <= 9 in place.
Solution
#include <string>
void multiplyByDigit(std::string& num, int n) {
int carry = 0;
for (char& ch : num) { // from the least-significant digit
int product = (ch - '0') * n + carry;
ch = char('0' + product % 10);
carry = product / 10;
}
while (carry > 0) { // append high-order digits
num.push_back(char('0' + carry % 10));
carry /= 10;
}
}Key points
product = digit * n + carry; store% 10, carry/ 10.- The leftover carry is appended as new high-order digits.
- No
long long: a big number does not fit a fixed-width type.
Contents
