count_of_trailing_ciphers_in_factorial_n.cpp File Reference

Count the number of ciphers in n! implementation More...

#include <cassert>
#include <iostream>

Include dependency graph for count_of_trailing_ciphers_in_factorial_n.cpp:

Namespaces
namespace	bit_manipulation
	for IO operations
namespace	count_of_trailing_ciphers_in_factorial_n
	Functions for the Count the number of ciphers in n! implementation.

Functions
uint64_t	bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN (uint64_t n)
	Function to count the number of the trailing ciphers.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Count the number of ciphers in n! implementation

Given an integer number as input. The goal is to find the number of trailing zeroes in the factorial calculated for that number. A factorial of a number N is a product of all numbers in the range [1, N].

We know that we get a trailing zero only if the number is multiple of 10 or has a factor pair (2,5). In all factorials of any number greater than 5, we have many 2s more than 5s in the prime factorization of that number. Dividing a number by powers of 5 will give us the count of 5s in its factors. So, the number of 5s will tell us the number of trailing zeroes.

Author

Swastika Gupta

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

numberOfCiphersInFactorialN()

uint64_t bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN

(

uint64_t

n

)

Function to count the number of the trailing ciphers.

Parameters

n	number for which n! ciphers are returned

Returns

count, Number of ciphers in n!.

                                                 {
    // count is to store the number of 5's in factorial(n)
    uint64_t count = 0;
 
    // Keep dividing n by powers of
    // 5 and update count
    for (uint64_t i = 5; n / i >= 1; i *= 5) {
        count += static_cast<uint64_t>(n) / i;
    }
 
    return count;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    // 1st test
    std::cout << "1st test ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
               numberOfCiphersInFactorialN(395) == 97);
    std::cout << "passed" << std::endl;
 
    // 2nd test
    std::cout << "2nd test ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
               numberOfCiphersInFactorialN(977) == 242);
    std::cout << "passed" << std::endl;
 
    // 3rd test
    std::cout << "3rd test ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
               numberOfCiphersInFactorialN(871) == 215);
    std::cout << "passed" << std::endl;
 
    // 4th test
    std::cout << "4th test ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
               numberOfCiphersInFactorialN(239) == 57);
    std::cout << "passed" << std::endl;
 
    // 5th test
    std::cout << "5th test ";
    assert(bit_manipulation::count_of_trailing_ciphers_in_factorial_n::
               numberOfCiphersInFactorialN(0) == 0);
    std::cout << "passed" << std::endl;
}

Here is the call graph for this function: