Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Factorial vs Exponential

Original Problem

Goal

For each of the given numbers \(A\), find the smallest integer \(N\), such that \(A^N < N!\) , where \(N! = 1 \cdot 2 \cdot ... \cdot N\)
The numbers given can have up to 2 digits after decimal point.
Input
Line 1: An integer \(K\) for the number of inputs.
Line 2: \(K\) space separated numbers (can have a fractional part, e.g. 1.5): \( A_1 , A_2 , ... , A_K\)
Output
Line 1: \(K\) space separated integers: \( N_1 , N_2 , ... , N_K\) .
Constraints
\(1 ≤ K ≤ 100\)
\(1 < A_i < 10000\)

Solution

I first thought it's a fun number theoretic problem again, similar to dividing the factorial, where Legendre's formula could be used. However, \(A\) is a decimal number and so the whole thing doesn't make sense anymore. The only thing we can do is the following:

\[A^N< N!\Leftrightarrow N<\log_A{N!} = \sum\limits_{i=1}^N\log_Ai = \frac{1}{\log A} \sum\limits_{i=1}^N\log i\]

It follows that we simply loop over the logarithms until the stated condition breaks. The last integer \(N\) we see this way is the smallest fulfilling the initial statement.

var K = +readline();
var inputs = readline().split(' ');
var R = [];

for (var k = 0; k < K; k++) {
    var A = parseFloat(inputs[k]);

    var s = 0;
    var logA = Math.log(A);
    for (var i = 1; ; i++) {
        s+= Math.log(i);
        if (i * logA < s) break;
    }
    R.push(i);
}
print(R.join(" "));

« Back to problem overview