2021-05-16: the time complexity must be logN, how to find the first number from right to left that is not zero?

Answer 2021-05-16:

The logN solution is a big step, which is very hard to find on the Internet. In addition, in terms of code simplicity, my code is clearly the simplest. When you look at the code, you’re going to be very disappointed. Because it’s so easy when you can’t even think about it.

Let’s say the number is N. 1. If N is divisible by 5, use the large step method. N becomes N over 5. 1.1. When N is divisible by 4. When N is equal to 20, f of 20 is equal to f of 4. 1.2. When N is divisible by 4, remainder 1. When N is equal to 5, f of 5 is equal to 2f of 1. 1.3. When N is divisible by 4, remainder 2. When N is equal to 10, f of 10 is equal to 4f of 2. When N is divisible by 4, the remainder is 3. When N is equal to 15, f of 15 is equal to 8 times f of 3. Combine these four scenarios. F of N is equal to 2 to the N&3 times f of N over 5. 2. If N cannot be divisible by 5, use small steps. N becomes N minus 1. When N=27, f(27)= 27%10, f(26)=7f(26).

The code is written in Golang. The code is as follows:

package main

import "fmt"

func main(a) {

    for i := 1; i <= 3125; i++ {
        fmt.Println(i, FactRightNotZero(i))
    }

}

func FactRightNotZero(n int) int {
    ans := 1
    for n > 0 {
        if n%5= =0 {
            ans <<= n & 3 // This is the essence
            n /= 5
        } else {
            ans *= n % 10
            n--
        }
        ans %= 10
    }
    return ans
}
Copy the code

The result is as follows: