leetcode-go/written-exam/hulu-2019-interview/main.go

// The exponential of 11

// 3fsv3 - collabedit.com

package main

import "fmt"

// Node ...
type Node struct {
	val  int
	next *Node
}

func reverse(head *Node) *Node {
	if head == nil || head.next == nil {
		return head
	}
	dummy := Node{-1, nil}
	tail := head.next
	for tail != nil {
		tmp := tail.next
		tail.next = dummy.next
		dummy.next = tail
		tail = tmp
	}
	head.next = dummy.next
	return head
}

func pow(n int) string {
	base := []byte{'1', '1'}
	res := []byte{'1'}
	for n != 0 {
		if n&1 == 1 {
			res = mul(res, base)
		}
		base = mul(base, base)
		n >>= 1
	}
	for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
		res[l], res[r] = res[r], res[l]
	}
	return string(res)
}

func mul(a, b []byte) []byte {
	m, n := len(a), len(b)
	c := make([]byte, m+n)
	for i := range c {
		c[i] = '0'
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			res := (a[i] - '0') * (b[j] - '0')
			c[i+j] += res
		}
	}
	mod := 0
	for i := 0; i < len(c); i++ {
		c[i] += byte(mod)
		mod = int(c[i]-'0') / 10
		c[i] = byte(int(c[i]-'0')%10 + '0')
	}
	i := m + n
	for ; 1 <= i; i-- {
		if c[i-1] != '0' {
			break
		}
	}
	if i == 0 {
		return c[:i+1]
	}
	return c[:i]
}

func main() {
	fmt.Println(pow(9999))
}