(C#) Factorial Trailing Zeroes Create a function that, given a positive integer n,…
- User
(C#) Factorial Trailing Zeroes Create a function that, given a positive integer n, returns the number of trailing zeroes in n!.
Examples TrailingZeroes(6) ➞ 1 // factorial(6) = 720
TrailingZeroes(30) ➞ 7 // factorial(30) = 265252859812191058636308480000000 Notes Create a solution that works in logarithmic time complexity. n! = n * (n-1) * (n-2) * ... * 2 * 1
- Assistant
To solve this problem efficiently, we need to find out how many times the number 10 is a factor in n!. Every trailing zero in n! comes from a pair of 2 and 5 factors (since 2 * 5 = 10). In a factorial, there are typically more factors of 2 than 5, so the number of trailing zeros is determined by the number of times 5 is a factor in n!.
Here's how we can calculate the number of trailing zeros:
- Initialize a count variable to 0: This will keep track of the total number of factors of 5 in n!.
- Divide n by 5: This gives the number of multiples of 5 between 1 and n.
- Add the result to the count.
- Repeat step 2 and 3 for higher powers of 5 (i.e., 25, 125, etc.): This accounts for numbers like 25, 125, etc., which contribute more than one 5 to the factorial.
Here's the C# function implementing the above logic:
public class Program { public static int TrailingZeroes(int n) { int count = 0; while(n >= 5) { n /= 5; count += n; } return count; } }Explanation:
- We use a
whileloop that continues as long asnis greater than or equal to 5. - In each iteration, we divide
nby 5 and add the quotient tocount. - This process efficiently calculates the total number of 5s in the prime factors of n!, thus giving us the number of trailing zeros.
Examples:
TrailingZeroes(6)returns1because 6! = 720, which has one trailing zero.TrailingZeroes(30)returns7because 30! has seven trailing zeros.
This function runs in logarithmic time complexity relative to the input number
n, as it reducesnby a factor of 5 in each iteration of the loop.