How to find the number of trailing zeros of N in Rust

The challenge

Write a program that will calculate the number of trailing zeros in a factorial of a given number.

N! = 1 * 2 * 3 * ... * N

Be careful 1000! has 2568 digits…

For more info, see: http://mathworld.wolfram.com/Factorial.html

Examples

zeros(6) = 1 # 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 --> 1 trailing zero zeros(12) = 2 # 12! = 479001600 --> 2 trailing zeros
Code language: PHP (php)

The solution in Rust

Option 1:

fn zeros(n: u64) -> u64 { if n == 0 { 0 } else { n / 5 + zeros(n / 5) } }
Code language: Rust (rust)

Option 2:

fn zeros(n: u64) -> u64 { (1..) .map(|exp| n / 5_u64.pow(exp)) .take_while(|&x| x != 0) .sum() }
Code language: Rust (rust)

Option 3:

fn zeros(n: u64) -> u64 { let max = (n as f64).log(5.0).floor() as u32; (1..=max).fold(0, |acc, i| acc + n / 5_u64.pow(i)) }
Code language: Rust (rust)

Test cases to validate our solution

#[cfg(test)] mod tests { use super::*; #[test] fn fixed_tests() { assert_eq!(zeros(0), 0); assert_eq!(zeros(6), 1); assert_eq!(zeros(14), 2); assert_eq!(zeros(30), 7); assert_eq!(zeros(1000), 249); assert_eq!(zeros(100000), 24999); assert_eq!(zeros(1000000000), 249999998); } fn solution(n: u64) -> u64 { let mut r = 0; let mut n = n / 5; while n > 0 { r += n; n /= 5; } r } use rand::Rng; #[test] fn random_tests() { let mut rng = rand::thread_rng(); for _i in 0..100 { let n: u64 = rng.gen_range(0..1001); let expected = solution(n); let actual = zeros(n); assert_eq!(actual, expected, "zeros({}): expected {}, got {}", n, expected, actual); } for _i in 0..100 { let n: u64 = rng.gen_range(0..1000001); let expected = solution(n); let actual = zeros(n); assert_eq!(actual, expected, "zeros({}): expected {}, got {}", n, expected, actual); } for _i in 0..100 { let n: u64 = rng.gen_range(0..1000000001); let expected = solution(n); let actual = zeros(n); assert_eq!(actual, expected, "zeros({}): expected {}, got {}", n, expected, actual); } } }
Code language: Rust (rust)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments