Software Engineering

How to Find the Last Fibonacci Digit in Golang


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).

LastFibDigit(1) == 1
LastFibDigit(2) == 1
LastFibDigit(3) == 2
LastFibDigit(1000) == 5
LastFibDigit(1000000) == 5

The solution in Golang

Option 1:

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:

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:

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

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))
  })
})