Problem Statement: Given an integer n and base B, the task is to find the length of n! in base B.
Sample Problem Link: http://lightoj.com/volume_showproblem.php?problem=1045
In this problem set you can use Kamnestsky's Algorithm
Approach:
In order to solve the problem we use Kamenetsky’s formula which approximates the number of digits in a factorial:
f(x) = log10( ((n/e)^n) * sqrt(2*pi*n))
The number of digits in n to the base b is given by-
logb(n) = log10(n) / log10(b)
Hence, by using properties of logarithms, the number of digits of factorial in base b can be obtained by -
f(x) = ( n* log10(( n/ e)) + log10(2*pi*n)/2 ) / log10(b)
This approach can deal with large inputs that can be accommodated in a 32-bit integer and even beyond that!
Solve Link: https://github.com/Remonhasan/algorithm/blob/master/Kamenetsky%20-Algorithm.cpp
Oldest comments (0)