The challenge
Return the last digit of the nth element in the Fibonacci sequence (starting with 1,1, to be extra clear, not with 0,1 or other numbers).
1
2
3
4
5
|
LastFibDigit(1) == 1
LastFibDigit(2) == 1
LastFibDigit(3) == 2
LastFibDigit(1000) == 5
LastFibDigit(1000000) == 5
|
The solution in Golang
Option 1:
1
2
3
4
5
6
7
|
package solution
func LastFibDigit(n int) int {
n %= 60
a, b := 0, 1
for i := 0; i<n; i++ { a, b = b, a+b }
return a % 10
}
|
Option 2:
1
2
3
4
5
6
7
8
9
|
package solution
func LastFibDigit(n int) int {
fib := []int{0, 1}
for i := 1; i < 60; i++ {
fib = append(fib, (fib[i]+fib[i-1])%10)
}
j := n % 60
return fib[j]
}
|
Option 3:
1
2
3
4
5
|
package solution
import "math"
func LastFibDigit(n int) int {
return int(math.Pow(math.Phi, float64(n%60))/math.Sqrt(5) + 0.5) % 10
}
|
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
|
package solution_test
import (
. "github.com/onsi/ginkgo"
. "github.com/onsi/gomega"
)
var _ = Describe("Sample test cases", func() {
It("Basic tests", func() {
Expect(LastFibDigit(1)).To(Equal(1))
Expect(LastFibDigit(21)).To(Equal(6))
Expect(LastFibDigit(302)).To(Equal(1))
Expect(LastFibDigit(4003)).To(Equal(7))
Expect(LastFibDigit(50004)).To(Equal(8))
Expect(LastFibDigit(600005)).To(Equal(5))
Expect(LastFibDigit(7000006)).To(Equal(3))
Expect(LastFibDigit(80000007)).To(Equal(8))
Expect(LastFibDigit(900000008)).To(Equal(1))
Expect(LastFibDigit(1000000009)).To(Equal(9))
})
})
|
