CtCI - Grade School Algorithm

CtCI - Grade School Algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.

We usually learn this in 1st-2nd grade as the easiest method to multiply two big numbers apparently because it is easier to visualize the values for the subsequent operation (which is a sum) to get to the desired results.

For a multi-digit number 5678 we want to visualize the grade-school algorithm when it is multiplied by 1234 including the raised numbers and the middle sums before we print the result to the user.

# Input
5678x1234
# Output
   5678
   1234 *
-------
  22712 +
 17034~
11356~~
5678~~~
-------
7006652

Solution

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func padleft(text string, length int) string {
    var total = len(text)

    if total < length {
        text = strings.Repeat("\x20", length-total) + text
    }

    return text
}

func main() {
    var line string
    var sections []string

    fmt.Scanf("%s", &line)

    parts := strings.Split(line, "x")

    if len(parts) < 2 {
        fmt.Println("Usage: echo \"5678x1234\" | solution")
        return
    }

    step := 0
    total := 0
    longest := 0
    base := parts[0]
    multiplier := parts[1]
    blength := len(base)
    mlength := len(multiplier)

    sections = append(sections, base)
    sections = append(sections, multiplier)
    sections = append(sections, "") /* separator */

    for m := mlength - 1; m >= 0; m-- {
        remain := 0
        subtotal := ""
        num := int(multiplier[m] - '0')

        for n := blength - 1; n >= 0; n-- {
            baseint := int(base[n] - '0')
            result := (baseint * num) + remain
            resultstr := strconv.Itoa(result)

            if result > 9 {
                subtotal = string(resultstr[1]) + subtotal
                remain = int(resultstr[0] - '0')
            } else {
                subtotal = resultstr + subtotal
                remain = 0
            }
        }

        if remain > 0 {
            subtotal = strconv.Itoa(remain) + subtotal
        }

        submult := subtotal + strings.Repeat("~", step)
        submultstr := subtotal + strings.Repeat("0", step)
        submultint, _ := strconv.Atoi(submultstr)

        total += submultint

        if len(submult) > longest {
            longest = len(submult)
        }

        sections = append(sections, submult)
        step++
    }

    for key, text := range sections {
        sections[key] = padleft(text, longest)
    }

    sections[1] += "\x20*"
    sections[3] += "\x20+"
    sections[2] = strings.Repeat("-", longest) /* separator */
    sections = append(sections, sections[2])   /* separator */
    sections = append(sections, strconv.Itoa(total))

    fmt.Println(strings.Join(sections, "\n"))
}
Do you have a project idea? Let's make it together!