DEV Community

loading...
Cover image for Kamenetsky's Algorithm

Kamenetsky's Algorithm

remonhasan profile image Remon Hasan ・1 min read

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

Discussion

pic
Editor guide