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"))
}
20 days ago
  • 8da57acFix minor bugs found by the code static ana…
20 days ago
  • caa417fAdd option to configure the malware scanner…
21 days ago
  • 9c86744Modify default value for some of the alert …
21 days ago
  • 84dd39dAdd option to stop sending the failed login…
21 days ago
  • eb05935Add pre-checks for every plugin page for si…
21 days ago
  • d21a062Modify mechanism to ignore files from integ…
22 days ago
  • b1a9169Add developer option to disable failed pass…
23 days ago
  • 4e3ef13Add support for other English and Spanish b…
23 days ago
  • 2d07b4eFix error interception for Firewall API err…
24 days ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
24 days ago
pushed to master at cixtor/slackapi
25 days ago
  • 6497e80Remove unnecessary automatic blacklisting o…
25 days ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
25 days ago
25 days ago
28 days ago
  • 38cc02aModify timing for the dashboard alerts afte…
28 days ago
  • 350c074Fix infinite loop with email alerts and SMT…
28 days ago
  • acff4aaFix detection of base URL with built-in fun…
28 days ago
29 days ago
29 days ago
30 days ago
30 days ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
30 days ago
1 month ago
  • 4c51445Fix static function call of non-static Site…
1 month ago
1 month ago
  • af47581Add changelog to release version 1.8.6
1 month ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
1 month ago
  • dc1a05aAdd changelog to release version 1.8.5
1 month ago
Do you have a project idea? Let's make it together!