Digit-by-digit arithmetic

When to use it

Use it when a number comes as separate digits in a list, a string or linked nodes, or when you must take its digits off one at a time.

It belongs to the math & bits group: Work on the cells, the digits or the bits themselves, in a fixed order.

Watch it work

A quiz show keeps the prize on a board, one digit on each panel. In the last round the prize is multiplied by a number from 2 to 9. Return the digits the board must show after that.

Input
digits = [2, 9, 0, 7]
times = 4

Output
[1, 1, 6, 2, 8]

The method

1. Start at the last digit with a carry of 0
2. Multiply the digit and add the carry from the right
3. Write the last digit of the total; carry the rest left
4. A carry left at the end becomes a new first digit
5. Return the digits of the product

The run, one moment at a time

1. Step 1. The board shows 2907, and the prize is multiplied by 4. Start at the last digit, 7, with a carry of 0. The product has 4 places, all still 0.

   digits: 2 9 0 7
   carry: 0
   total: empty
   product: 0 0 0 0
   

2. Step 2. The digit is 7. 7 × 4 = 28. The carry is 0, so the total is 28.

   digits: 2 9 0 7
   carry: 0
   total: 28
   product: 0 0 0 0
   

3. Step 3. 28 does not fit in one place. Write its last digit, 8, and carry 2 to the place on the left.

   digits: 2 9 0 7
   carry: 2
   total: 28
   product: 0 0 0 8
   

4. Step 2. The digit is 0. 0 × 4 = 0. Add the carry 2 from the right: the total is 2.

   digits: 2 9 0 7
   carry: 2
   total: 2
   product: 0 0 0 8
   

5. Step 3. 2 fits in one place. Write 2. Nothing is left over, so the carry goes back to 0.

   digits: 2 9 0 7
   carry: 0
   total: 2
   product: 0 0 2 8
   

6. Step 2. The digit is 9. 9 × 4 = 36. The carry is 0, so the total is 36.

   digits: 2 9 0 7
   carry: 0
   total: 36
   product: 0 0 2 8
   

7. Step 3. 36 does not fit in one place. Write its last digit, 6, and carry 3 to the place on the left.

   digits: 2 9 0 7
   carry: 3
   total: 36
   product: 0 6 2 8
   

8. Step 2. The digit is 2. 2 × 4 = 8. Add the carry 3 from the right: the total is 11.

   digits: 2 9 0 7
   carry: 3
   total: 11
   product: 0 6 2 8
   

9. Step 3. 11 does not fit in one place. Write its last digit, 1, and keep 1 as the carry. This was the first digit, so no place is left to take it.

   digits: 2 9 0 7
   carry: 1
   total: 11
   product: 1 6 2 8
   

10. Step 4. No digit is left, but the carry is 1. It becomes a new first digit, so the product has 5 digits, one more than the prize had.

    digits: 2 9 0 7
    carry: 1
    total: empty
    product: 1 1 6 2 8
    

11. Step 5. The board now shows 11628, and 2907 × 4 = 11628. Each digit was used once, and the carry was never more than 3.

    digits: 2 9 0 7
    carry: 1
    total: empty
    product: 1 1 6 2 8
    

The code

The numbered comments are the steps of the method.

function solve(digits, times) {
  // 1. Start at the last digit with a carry of 0
  const product = new Array(digits.length).fill(0);
  let carry = 0;
  for (let i = digits.length - 1; i >= 0; i--) {
    // 2. Multiply the digit and add the carry from the right
    const total = digits[i] * times + carry;
    // 3. Write the last digit of the total; carry the rest left
    product[i] = total % 10;
    carry = Math.floor(total / 10);
  }
  // 4. A carry left at the end becomes a new first digit
  if (carry > 0) product.unshift(carry);
  // 5. Return the digits of the product
  return product;
}

def solve(digits, times):
    # 1. Start at the last digit with a carry of 0
    product = [0] * len(digits)
    carry = 0
    for i in reversed(range(len(digits))):
        # 2. Multiply the digit and add the carry from the right
        total = digits[i] * times + carry
        # 3. Write the last digit of the total; carry the rest left
        product[i] = total % 10
        carry = total // 10
    # 4. A carry left at the end becomes a new first digit
    if carry > 0:
        product.insert(0, carry)
    # 5. Return the digits of the product
    return product

How to spot it

Given: A number given as a list of digits, or one digit to a node

The number is already cut into places. Do the arithmetic one place at a time, and pass a carry on to the next place.

Limits: You may not turn the whole string into a number

The built-in arithmetic is ruled out, and in many languages a long number would not fit. The paper method needs only one digit and a carry.

Asked: The result may need one more digit than the input has

That extra digit is the carry left over after the first digit. A carry means the arithmetic is done place by place.

Asked: A question about the digits of a whole number, such as their sum

The remainder after dividing by 10 is the last digit. Dividing by 10 and rounding down removes it. Repeat, and the number comes apart digit by digit.

Looks like it, but is not

• The task is about the 0s and 1s a number is stored as, such as testing one of them. Use Bit manipulation. Bits have operators of their own that test, flip or move them directly. Nothing is carried by hand from one place to the next.
• The digits sit in a linked list, and you must only put them in another order. Use Linked list pointer rewiring. Nothing is calculated and no carry is passed. Only the links between the nodes change.
• A string of digits must be cut into pieces in every way the rules allow. Use Backtracking. The digits are not places of one number here. Each cut is a choice that is tried and then undone.

Cost and mistakes

Time is one multiplication for each digit, about n steps for n digits, written O(n). Extra space is the digits of the answer, also O(n), and one carry, which is never more than 8 for a multiplier up to 9.

Watch out

• Do not stop when the digits run out. A carry that is still there becomes a new digit in front: 50 × 2 is 100, and without the last carry you would return 00.
• Start at the digit worth least, because a carry moves toward the bigger places. Here that is the last item. If the number is stored the other way round, it is the first.

In the 150

5 problems of the 150 use it. Naming them gives their method away, so the list is folded.