Friday, November 24, 2023
HomeSoftware EngineeringLearn how to Discover the Final Digit of a Big Quantity in...

Learn how to Discover the Final Digit of a Big Quantity in Golang


The problem

For a given record [x1, x2, x3, ..., xn] compute the final (decimal) digit of x1 ^ (x2 ^ (x3 ^ (... ^ xn))).

Instance:

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

as a result of 3 ^ (4 ^ 2) = 3 ^ 16 = 43046721.

Beware: powers develop extremely quick. For instance, 9 ^ (9 ^ 9) has greater than 369 thousands and thousands of digits. lastDigit has to take care of such numbers effectively.

Nook instances: we assume that 0 ^ 0 = 1 and that lastDigit of an empty record equals to 1.

The answer in Golang

Choice 1:

package deal answer
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
}

Choice 2:

package deal answer
import "math"
func LastDigit(as []int) (outcome int) {
  if len(as) == 0 {
    return 1
  }
  p := 1
  for i := len(as) - 1; i >= 0; i-- {
    outcome = low(as[i], 40)
    outcome = int(math.Pow(float64(outcome), float64(p)))
    p = low(outcome, 4)
  }
  return outcome % 10
}
func low(i int, base int) int {
  if i > base {
    i = ipercentbase + base
  }
  return i
}

Choice 3:

package deal answer
import "math/huge"
func LastDigit(as []int) int {
  if (len(as)==0) { return 1 }
  r:=huge.NewInt(1)
  f:=huge.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(huge.NewInt(int64(as[i])),r,nil)
  }
  return int(r.Mod(r,huge.NewInt(10)).Int64())
}

Check instances to validate our answer

package deal solution_test

import (
  . "math/rand"
  . "math"
  . "github.com/onsi/ginkgo"
  . "github.com/onsi/gomega"
)

var _ = Describe("Check Instance", func() {
  It("ought to deal with primary instances", func() {
    Anticipate(LastDigit( []int{}                     )).To(Equal(1))
    Anticipate(LastDigit( []int{0,0}                  )).To(Equal(1)) // 0 ^ 0
    Anticipate(LastDigit( []int{0,0,0}                )).To(Equal(0)) // 0^(0 ^ 0) = 0^1 = 0
    Anticipate(LastDigit( []int{1,2}                  )).To(Equal(1))
    Anticipate(LastDigit( []int{3,4,5}                )).To(Equal(1))
    Anticipate(LastDigit( []int{4,3,6}                )).To(Equal(4))
    Anticipate(LastDigit( []int{7,6,21}               )).To(Equal(1))
    Anticipate(LastDigit( []int{12,30,21}             )).To(Equal(6))
    Anticipate(LastDigit( []int{2,0,1}                )).To(Equal(1))
    Anticipate(LastDigit( []int{2,2,2,0}              )).To(Equal(4))
    Anticipate(LastDigit( []int{937640,767456,981242} )).To(Equal(0))
    Anticipate(LastDigit( []int{123232,694022,140249} )).To(Equal(6))
    Anticipate(LastDigit( []int{499942,898102,846073} )).To(Equal(6))
  })
  
  It("ought to deal with random instances", func() {
    var r1 int = Intn(100)
    var r2 int = Intn(10)
    var pow int = int(Pow(float64(r1 % 10), float64(r2)))

    Anticipate(LastDigit( []int{}       )).To(Equal(1))
    Anticipate(LastDigit( []int{r1}     )).To(Equal(r1 % 10))
    Anticipate(LastDigit( []int{r1, r2} )).To(Equal(pow % 10))
  })
})
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments