未分類

Factorial Trailing Zeroes

Go, LeetCode, Math

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note:

Your solution should be in logarithmic time complexity.

提示 解題應用
Math 觀查規律

Default:

1
2
3
func trailingZeroes(n int) int {
}

解答思路:

這題時間上訂的滿嚴格，只要沒有用對方法基上都不會過，而在n!要求後頭有幾個0最重要的在於怎麼湊到0，既然有0想必為10的倍數才有可能，而10進而拆開的話是2與5做相乘，所以在乘階上要湊到尾數有0相必至少有相應數量的2與5，而2的數量光是2與4與6及8的倍數就太多了，觀查會發現尾數有多少個0在乘階上就會有多少個5的倍數，如此一來我們只要找出5的倍數有多少個就可以了，在一開始我用一回圈遍歷5的倍數直到小於給的n!，之中再一回圈去算該數的5的倍數共有多少個5的乘積，但是仍然超過時間，因為有更簡單的方式，直接將n!的n去除5，再除25、125…一直到n/(5的x次方)為0，就可以直接算出n!因式分解後共有多少個5的乘積，等同推出結果尾數有多少個0。

程式碼解說:

有了公式就是不斷的將n!的n去除以5的次方總合後，再來就是用迴圈不斷將n去除5的次方，然後將每次除完的結果做總合，再將除數乘上5繼續重覆執行，直到要增加至總合的結果為0才跳開回圈回傳總合

1
2
3
4
5
6
7
8
9
var count int
tmp := 5
mult5 := n / tmp
for mult5 != 0 {
	count = count + mult5
	tmp = tmp * 5
	mult5 = n / tmp
}
return count

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
func trailingZeroes(n int) int {
	var count int
	tmp := 5
	mult5 := n / tmp
	for mult5 != 0 {
		count = count + mult5
		tmp = tmp * 5
		mult5 = n / tmp
	}
	return count
}

總結:

n!要求後頭有幾個0，想必為10的乘積有多少個，間接推出5的乘積有多少個，畢竟2的乘積數量足夠多了，所以重點在於5，而n!因式分解後要知道有多少個5的乘積數最簡單的方式如下:

n!的5乘積數 = [n/5] + [n/25] + [n/125] … + ([n/5的某次方]此值為0為止)

分享到