Problem: Count digits in a factorial

Given an integer n,  find the number of digits that appear in its factorial, where factorial is defined as, factorial(n) = 1*2*3*4……..*n and factorial(0) = 1.

Input:

The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of one line. The first line of each test case consists of an integer N.

Output:

Corresponding to each test case, in a new line, print the number of digits that appear in its factorial.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 10000

Example:

Input
2
5
120

Output
3

199

There is unclean way of solving it.

Number of digits in a number ‘N’ is CEILING(log(N)).

So number of digit in N! is CEILING(log(N!)) = CEILING(log(N*(N-1)*(N-2)) … 2*1)

Thus,

CEILING(log(N!)) = CEILING(log(N) + log(N-1) +log(N-2)+ … log(2)*log(1))
Which is pretty easy to compute.

Python 2.7:

from math import log
from math import ceil
def digits_of_fact(n):
    if n <= 2:
        return 1
    digits = 0
    for _ in range(2, n+1):
        digits += log(_, 10)
    return int(ceil(digits))

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
        print digits_of_fact(n)

 

Advertisements