package main

import (
	"fmt"
	"strconv"
)

// length < 110, non-negative
func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	if num1 == "1" {
		return num2
	} else if num2 == "1" {
		return num1
	}
	n1 := str2IntSlice(num1)
	n2 := str2IntSlice(num2)
	sum := []int{}
	if len(n1) < len(n2) {
		n1, n2 = n2, n1
	}
	for index, num := range n2 {
		product := intSliceMulInt(n1, num)
		zeros := make([]int, len(n2)-1-index)
		product = append(product, zeros...)
		sum = addIntSlice(sum, product)
	}
	return intSlice2Str(sum)
}

func str2IntSlice(str string) []int {
	res := []int{}
	for _, char := range str {
		res = append(res, int(char-'0'))
	}
	return res
}

func intSlice2Str(slice []int) string {
	str := []rune{}
	for _, i := range slice {
		str = append(str, rune(i+'0'))
	}
	return string(str)
}

func addIntSlice(slice1, slice2 []int) []int {
	if len(slice1) < len(slice2) {
		slice1, slice2 = slice2, slice1
	}
	if len(slice2) == 0 || (len(slice2) == 1 && slice2[0] == 0) {
		return slice1
	}
	res := make([]int, len(slice1)+1)
	carry := 0
	for offset := 0; offset < len(slice1); offset++ {
		var digit, digit1, digit2 int
		if offset < len(slice2) {
			digit1 = slice1[len(slice1)-1-offset]
			digit2 = slice2[len(slice2)-1-offset]
		} else if offset < len(slice1) {
			digit1 = slice1[len(slice1)-1-offset]
			digit2 = 0
		} else {
			digit1, digit2 = 0, 0
		}
		digit, carry = addByDigit(digit1, digit2, carry)
		res[len(res)-1-offset] = digit
	}
	if carry == 0 {
		return res[1:]
	}
	res[0] = carry
	return res
}

func intSliceMulInt(slice []int, num int) []int {
	if num == 0 || len(slice) == 0 || (len(slice) == 1 && slice[0] == 0) {
		return []int{0}
	}
	if num == 1 {
		return slice
	}
	res := make([]int, len(slice)+1)
	carry := 0
	for offset := 0; offset < len(slice); offset++ {
		digit := slice[len(slice)-1-offset]
		digit, carry = mulByDigit(digit, num, carry)
		res[len(res)-1-offset] = digit
	}
	if carry == 0 {
		return res[1:]
	}
	res[0] = carry
	return res
}

func mulByDigit(digit1, digit2, lastCarry int) (digit, carry int) {
	digit = digit1*digit2 + lastCarry
	carry = digit / 10
	return digit % 10, carry
}

func addByDigit(digit1, digit2, lastCarry int) (digit, carry int) {
	digit = digit1 + digit2 + lastCarry
	carry = digit / 10
	return digit % 10, carry
}

func testMultiply(num1 string, num2 string) {
	n1, _ := strconv.Atoi(num1)
	n2, _ := strconv.Atoi(num2)
	fmt.Printf("%s * %s = %s | %d\n", num1, num2, multiply(num1, num2), n1*n2)
	slice := str2IntSlice("12347876")
	intSlice2Str(slice)
}

/* func main() {
	testMultiply("782", "3908982")
} */