## The challenge

For a given list `[x1, x2, x3, ..., xn]` compute the last (decimal) digit of `x1 ^ (x2 ^ (x3 ^ (... ^ xn)))`.

Example:

 ``````1 `````` ``````last_digit({3, 4, 2}, 3) == 1 ``````

because `3 ^ (4 ^ 2) = 3 ^ 16 = 43046721`.

Beware: powers grow incredibly fast. For example, `9 ^ (9 ^ 9)` has more than 369 millions of digits. `lastDigit` has to deal with such numbers efficiently.

Corner cases: we assume that `0 ^ 0 = 1` and that `lastDigit` of an empty list equals to 1.

## The solution in Golang

Option 1:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 `````` ``````package solution import "math" func LastDigit(as []int) int { var acc int = 1 for i := len(as) - 1; i >=0; i-- { exp := acc % 4 + 4 if (acc < 4) { exp = acc } base := as[i] % 20 + 20 if (as[i] < 20) { base = as[i] } acc = int(math.Pow(float64(base), float64(exp))) } return acc % 10 } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````package solution import "math" func LastDigit(as []int) (result int) { if len(as) == 0 { return 1 } p := 1 for i := len(as) - 1; i >= 0; i-- { result = low(as[i], 40) result = int(math.Pow(float64(result), float64(p))) p = low(result, 4) } return result % 10 } func low(i int, base int) int { if i > base { i = i%base + base } return i } ``````

Option 3:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````package solution import "math/big" func LastDigit(as []int) int { if (len(as)==0) { return 1 } r:=big.NewInt(1) f:=big.NewInt(4) for i:=len(as)-1; i>=0; i-- { if r.Cmp(f) >=0 { r = r.Mod(r,f) r = r.Add(r,f) } r = r.Exp(big.NewInt(int64(as[i])),r,nil) } return int(r.Mod(r,big.NewInt(10)).Int64()) } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````package solution_test import ( . "math/rand" . "math" . "github.com/onsi/ginkgo" . "github.com/onsi/gomega" ) var _ = Describe("Test Example", func() { It("should handle basic cases", func() { Expect(LastDigit( []int{} )).To(Equal(1)) Expect(LastDigit( []int{0,0} )).To(Equal(1)) // 0 ^ 0 Expect(LastDigit( []int{0,0,0} )).To(Equal(0)) // 0^(0 ^ 0) = 0^1 = 0 Expect(LastDigit( []int{1,2} )).To(Equal(1)) Expect(LastDigit( []int{3,4,5} )).To(Equal(1)) Expect(LastDigit( []int{4,3,6} )).To(Equal(4)) Expect(LastDigit( []int{7,6,21} )).To(Equal(1)) Expect(LastDigit( []int{12,30,21} )).To(Equal(6)) Expect(LastDigit( []int{2,0,1} )).To(Equal(1)) Expect(LastDigit( []int{2,2,2,0} )).To(Equal(4)) Expect(LastDigit( []int{937640,767456,981242} )).To(Equal(0)) Expect(LastDigit( []int{123232,694022,140249} )).To(Equal(6)) Expect(LastDigit( []int{499942,898102,846073} )).To(Equal(6)) }) It("should handle random cases", func() { var r1 int = Intn(100) var r2 int = Intn(10) var pow int = int(Pow(float64(r1 % 10), float64(r2))) Expect(LastDigit( []int{} )).To(Equal(1)) Expect(LastDigit( []int{r1} )).To(Equal(r1 % 10)) Expect(LastDigit( []int{r1, r2} )).To(Equal(pow % 10)) }) }) ``````