Dare2Solve
The function calculates the number of trailing zeroes in the factorial of a given number ( n ). Trailing zeroes are formed by factors of 10 in the number, and each 10 is the result of multiplying 2 and 5. Since there are usually more factors of 2 than factors of 5 in a factorial, the number of trailing zeroes is determined by the number of times 5 is a factor in the numbers from 1 to ( n ).
To determine the number of trailing zeroes in ( n! ) (the factorial of ( n )), we need to count how many times 10 divides into ( n! ). Since 10 is made up of the prime factors 2 and 5, and there are typically more factors of 2 than 5, the number of trailing zeroes is determined by the number of times 5 is a factor. This is because every factor of 5 can pair with a factor of 2 to form a trailing zero.
( O(\log_5 n) ), as the number of iterations depends on the number of times 5 can be multiplied before exceeding ( n ).
( O(1) ), as the space used does not depend on the size of ( n ) but only on a few variables.
class Solution {
public:
int trailingZeroes(int n) {
int fives = 0;
for (int i = 5; i <= n; i *= 5) {
fives += n / i;
}
return fives;
}
};
class Solution:
def trailingZeroes(self, n: int) -> int:
fives = 0
i = 5
while i <= n:
fives += n // i
i *= 5
return fives
class Solution {
public int trailingZeroes(int n) {
int fives = 0;
for (int i = 5; i <= n; i *= 5) {
fives += n / i;
}
return fives;
}
}
/**
* @param {number} n
* @return {number}
*/
var trailingZeroes = function (n) {
let fives = 0;
for (let i = 5; i <= n; i *= 5) {
fives += Math.floor(n / i)
console.log(n, i)
}
return fives;
};