🎨 Try our Free AI Image Generation Feature

172. Factorial Trailing Zeroes

avatar
Dare2Solve

11 months ago

172. Factorial Trailing Zeroes

Description

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 ).

Intuition

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.

Approach

  1. Initialize a counter for the number of trailing zeroes.
  2. Iterate through powers of 5. For each power of 5, count how many numbers up to \( n \) are divisible by that power.
  3. Sum these counts to get the total number of factors of 5 in \( n! \).
  4. Return this sum as it represents the number of trailing zeroes in \( n! \).

Complexity

Time Complexity:

( O(\log_5 n) ), as the number of iterations depends on the number of times 5 can be multiplied before exceeding ( n ).

Space Complexity:

( O(1) ), as the space used does not depend on the size of ( n ) but only on a few variables.

Code

C++

class Solution {
public:
    int trailingZeroes(int n) {
        int fives = 0;
        for (int i = 5; i <= n; i *= 5) {
            fives += n / i;
        }
        return fives;
    }
};

Python

class Solution:
    def trailingZeroes(self, n: int) -> int:
        fives = 0
        i = 5
        while i <= n:
            fives += n // i
            i *= 5
        return fives

Java

class Solution {
    public int trailingZeroes(int n) {
        int fives = 0;
        for (int i = 5; i <= n; i *= 5) {
            fives += n / i;
        }
        return fives;
    }
}

JavaScript

/**
 * @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;
};