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