count_of_trailing_ciphers_in_factorial_n.cpp File Reference

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

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for count_of_trailing_ciphers_in_factorial_n.cpp:

Go to the source code of this file.

Namespaces
namespace	bit_manipulation
	for assert
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

Definition in file count_of_trailing_ciphers_in_factorial_n.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 96 of file count_of_trailing_ciphers_in_factorial_n.cpp.

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

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

Definition at line 41 of file count_of_trailing_ciphers_in_factorial_n.cpp.

                                                 {
    // 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;
}

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 60 of file count_of_trailing_ciphers_in_factorial_n.cpp.

                   {
    // 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;
}