LeetCode - 階乗の末尾のゼロ
5288 ワード
問題文
整数 n を指定すると、n! の末尾のゼロの数を返します.
n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
問題の説明: https://leetcode.com/problems/factorial-trailing-zeroes
例 1:
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.
例 2:
Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.
例 3:
Input: n = 0
Output: 0
制約:
- 0 <= n <= 10^4
説明
簡単な方法は、まず数値の階乗を計算してから、末尾のゼロの数を数えることです.上記の方法では、数値が大きいとオーバーフローが発生する可能性があります.
アイデアは、階乗 n の素因数を考慮することです.末尾のゼロは素因数 2 と 5 の結果です.2 と 5 の数を数えるだけです.
n = 5 の例を考えてみましょう.5! の素因数には 1 つの 5 と 3 つの 2 があります.
5! = 5 * 4 * 3 * 2 * 1
= 5 * 2^2 * 3 * 2
= 2^3 * 3 * 5
n = 11 の場合、2 つの 5 と 8 つの 2 があります.
11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
= 2^8 * 3^4 * 5^2 * 7 * 11
2 の数は 5 の数より多いと簡単に言えます.素因数の 5 の数を数えるだけで済みます.
n の素因数で 5 の数を数える!
最も簡単な方法は、floor(n/5) を計算することです.例えば7! 5、10が1つあります!は 2 つの 5 を持っています.しかし、n が 25、125 などの場合、5 は複数あります.29 を考慮すると!余分な 5 を取得し、後続のゼロの数は 6 になります.このケースを処理するには、まず n を 5 で割り、単一の 5 をすべて削除し、次に 25 で割って余分な 5 を削除します.
Trailing 0s in n! = floor(n/5) + floor(n/25) + floor(n/125) + ....
C++ ソリューション
class Solution {
public:
int trailingZeroes(int n) {
int count = 0;
for(long int i = 5; n / i >= 1; i *= 5){
count += n/i;
}
return count;
}
};
Golang ソリューション
func trailingZeroes(n int) int {
count := 0
for i := 5; n / i >= 1; i *= 5 {
count += n/i
}
return count
}
Javascript ソリューション
var trailingZeroes = function(n) {
let count = 0;
for( let i = 5; n / i >= 1; i *= 5 ) {
count += Math.floor(n / i);
}
return count;
};
アルゴリズムをドライランして、ソリューションがどのように機能するかを見てみましょう.
Input: n = 29
Step 1: count = 0
Step 2: loop for i = 5; n / i >= 1
28 / 5 >= 1
5 >= 1
true
count = count + n / i
= 0 + 29 / 5
= 0 + 5
= 5
i *= 5
i = 5 * 5
= 25
Step 3: n / i >= 1
28 / 25 >= 1
1 >= 1
true
count = count + n / i
= 5 + 29 / 25
= 5 + 1
= 6
i *= 5
= 25 * 5
= 125
Step 4: n / i >= 1
28 / 125 >= 1
0 >= 1
false
Step 5: return count
So we return the answer as 6.
Reference
この問題について(LeetCode - 階乗の末尾のゼロ), 我々は、より多くの情報をここで見つけました https://dev.to/_alkesh26/leetcode-factorial-trailing-zeroes-1f5aテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol