# Smallest number with at least n digits in factorial

Given a number n. The task is to find the smallest number whose factorial contains at least n digits.

Examples:

```Input : n = 1
Output : 0
0! = 1, hence it has 1 digit.

Input : n = 2
Output : 4
4! = 24 and 3! = 6, hence 4 is
the smallest number having 2
digits in its factorial

Input : n = 5
Output : 8
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

In the article for Count digits in a factorial of a number, we have discussed how we can efficiently find the number of digits in factorial.

We used the below formula to find the number of digits

```Kamenetsky’s formula approximates the number
of digits in a factorial by :
f(x) = log10(((n/e)n) * sqrt(2*pi*n))

Thus, we can pretty easily use the property of logarithms to ,
f(x) = n*log10((n/e)) + log10(2*pi*n)/2
```

Now we need to determine the interval in which we can find a factorial which has at least n digits. Following are some observations:

• For a large number we can always say that it’s factorial has more digits than the number itself. For example factorial of 100 has 158 digits which is greater than 100.
• However for smaller numbers, that might not be the case. For example factorial of 8 has only 5 digits, which is less than 8. In fact numbers up to 21 follow this trend.

Hence if we search from 0! to n! to find a result having at least n digits, we won’t be able to find the result for smaller numbers.

For example suppose n = 5, now as we’re searching in [0,n] the maximum number of digits we can obtain is 3, (found in 5! = 120). However if we search in [0, 2*n] (0 to 10), we can find 8! has 5 digits.

Hence, if we can search for all factorial from 0 to 2*n , there will always be a number k which will have at least n digits in its factorial.(Readers are advised to try on their own to figure out this fact)

```We can say conclude if we have to find a number k,
such that k! has at least n digits, we can be sure
that k lies in [0,2*n]

i.e., 0<= k <= 2*n

```

Thus we can do a binary search between 0 to 2*n to find the smallest number having at least n digits.

## C++

 `// A C++ program to find the smallest number ` `// having at least n digits in factorial ` `#include ` `using` `namespace` `std; ` ` `  `// Returns the number of digits present in n! ` `int` `findDigitsInFactorial(``int` `n) ` `{ ` `    ``// factorial of -ve number doesn't exists ` `    ``if` `(n < 0) ` `        ``return` `0; ` ` `  `    ``// base case ` `    ``if` `(n <= 1) ` `        ``return` `1; ` ` `  `    ``// Use Kamenetsky formula to calculate the ` `    ``// number of digits ` `    ``double` `x = ((n*``log10``(n/M_E)+``log10``(2*M_PI*n)/2.0)); ` ` `  `    ``return` `floor``(x)+1; ` `} ` ` `  `// This function receives an integer n and returns ` `// an integer whose factorial has at least n digits ` `int` `findNum(``int` `n) ` `{ ` `    ``// (2*n)! always has more digits than n ` `    ``int` `low = 0, hi = 2*n; ` ` `  `    ``// n <= 0 ` `    ``if` `(n <= 0) ` `        ``return` `-1; ` ` `  `    ``// case for n = 1 ` `    ``if` `(findDigitsInFactorial(low) == n) ` `        ``return` `low; ` ` `  `    ``// now use binary search to find the number ` `    ``while` `(low <= hi) ` `    ``{ ` `        ``int` `mid = (low+hi) / 2; ` ` `  `        ``// if (mid-1)! has lesser digits than n ` `        ``// and mid has n or more then mid is the ` `        ``// required number ` `        ``if` `(findDigits(mid) >= n && findDigits(mid-1)

## Java

 `// A Java program to find the  ` `// smallest number having at ` `// least n digits in factorial ` `class` `GFG ` `{ ` `// Returns the number of ` `// digits present in n! ` `static` `int` `findDigitsInFactorial(``int` `n) ` `{ ` `    ``// factorial of -ve number  ` `    ``// doesn't exists ` `    ``if` `(n < ``0``) ` `        ``return` `0``; ` ` `  `    ``// base case ` `    ``if` `(n <= ``1``) ` `        ``return` `1``; ` ` `  `    ``// Use Kamenetsky formula to  ` `    ``// calculate the number of digits ` `    ``double` `x = ((n * Math.log10(n / Math.E) +  ` `                     ``Math.log10(``2` `* Math.PI * n) / ``2.0``)); ` ` `  `    ``return` `(``int``)(Math.floor(x) + ``1``); ` `} ` ` `  `// This function receives an integer  ` `// n and returns an integer whose  ` `// factorial has at least n digits ` `static` `int` `findNum(``int` `n) ` `{ ` `    ``// (2*n)! always has ` `    ``// more digits than n ` `    ``int` `low = ``0``, hi = ``2` `* n; ` ` `  `    ``// n <= 0 ` `    ``if` `(n <= ``0``) ` `        ``return` `-``1``; ` ` `  `    ``// case for n = 1 ` `    ``if` `(findDigitsInFactorial(low) == n) ` `        ``return` `low; ` ` `  `    ``// now use binary search  ` `    ``// to find the number ` `    ``while` `(low <= hi) ` `    ``{ ` `        ``int` `mid = (low + hi) / ``2``; ` ` `  `        ``// if (mid-1)! has lesser digits ` `        ``// than n and mid has n or more  ` `        ``// then mid is the required number ` `        ``if` `(findDigitsInFactorial(mid) >= n && ` `            ``findDigitsInFactorial(mid - ``1``) < n) ` `            ``return` `mid; ` ` `  `        ``else` `if` `(findDigitsInFactorial(mid) < n) ` `            ``low = mid + ``1``; ` ` `  `        ``else` `            ``hi = mid - ``1``; ` `    ``} ` `    ``return` `low; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `main(String[] args) ` `{ ` `    ``System.out.println(findNum(``1``)); ` `    ``System.out.println(findNum(``2``)); ` `    ``System.out.println(findNum(``5``)); ` `    ``System.out.println(findNum(``24``)); ` `    ``System.out.println(findNum(``100``)); ` `    ``System.out.println(findNum(``1221``)); ` `} ` `} ` ` `  `// This Code is Contributed by mits `

## Python3

 `# Python3 program to find the  ` `# smallest number ` `# having at least n digits  ` `# in factorial ` ` `  `import` `math ` ` `  `# Returns the number of digits  ` `# present in n! ` `def` `findDigitsInFactorial(n): ` `     `  `    ``# factorial of -ve number  ` `    ``# doesn't exists ` `    ``if` `(n < ``0``): ` `        ``return` `0` ` `  `    ``# base case ` `    ``if` `(n <``=` `1``): ` `        ``return` `1` ` `  `    ``# Use Kamenetsky formula to calculate the ` `    ``# number of digits ` `    ``M_E``=``2.7182818284590452354` `    ``M_PI``=``3.14159265358979323846` `    ``x ``=` `((n``*``math.log10(n``/``M_E)``+``math.log10(``2``*``M_PI``*``n)``/``2.0``)) ` ` `  `    ``return` `int``(math.floor(x)``+``1``) ` ` `  `# This function receives an  ` `# integer n and returns ` `# an integer whose factorial has  ` `# at least n digits ` `def` `findNum(n): ` `     `  `    ``# (2*n)! always has more  ` `    ``# digits than n ` `    ``low ``=` `0` `    ``hi ``=` `2``*``n ` ` `  `    ``# n <= 0 ` `    ``if` `(n <``=` `0``): ` `        ``return` `-``1` ` `  `    ``# case for n = 1 ` `    ``if` `(findDigitsInFactorial(low) ``=``=` `n): ` `        ``return` `int``(``round``(low)) ` ` `  `    ``# now use binary search to  ` `    ``# find the number ` `    ``while` `(low <``=` `hi): ` `        ``mid ``=` `int``((low``+``hi) ``/` `2``) ` ` `  `        ``# if (mid-1)! has lesser digits than n ` `        ``# and mid has n or more then mid is the ` `        ``# required number ` `        ``if` `((findDigitsInFactorial(mid) >``=` `n ``and`  `            ``findDigitsInFactorial(mid``-``1``)

## C#

 `// A C# program to find the  ` `// smallest number having at  ` `// least n digits in factorial  ` `using` `System; ` ` `  `class` `GFG ` `{ ` `     `  `// Returns the number of  ` `// digits present in n!  ` `static` `int` `findDigitsInFactorial(``int` `n)  ` `{  ` `    ``// factorial of -ve number  ` `    ``// doesn't exists  ` `    ``if` `(n < 0)  ` `        ``return` `0;  ` ` `  `    ``// base case  ` `    ``if` `(n <= 1)  ` `        ``return` `1;  ` ` `  `    ``// Use Kamenetsky formula to  ` `    ``// calculate the number of digits  ` `    ``double` `x = ((n * Math.Log10(n / Math.E) +  ` `                     ``Math.Log10(2 * Math.PI * n) / 2.0));  ` ` `  `    ``return` `(``int``)(Math.Floor(x) + 1);  ` `}  ` ` `  `// This function receives an integer  ` `// n and returns an integer whose  ` `// factorial has at least n digits  ` `static` `int` `findNum(``int` `n)  ` `{  ` `    ``// (2*n)! always has  ` `    ``// more digits than n  ` `    ``int` `low = 0, hi = 2 * n;  ` ` `  `    ``// n <= 0  ` `    ``if` `(n <= 0)  ` `        ``return` `-1;  ` ` `  `    ``// case for n = 1  ` `    ``if` `(findDigitsInFactorial(low) == n)  ` `        ``return` `low;  ` ` `  `    ``// now use binary search  ` `    ``// to find the number  ` `    ``while` `(low <= hi)  ` `    ``{  ` `        ``int` `mid = (low + hi) / 2;  ` ` `  `        ``// if (mid-1)! has lesser digits  ` `        ``// than n and mid has n or more  ` `        ``// then mid is the required number  ` `        ``if` `(findDigitsInFactorial(mid) >= n &&  ` `            ``findDigitsInFactorial(mid - 1) < n)  ` `            ``return` `mid;  ` ` `  `        ``else` `if` `(findDigitsInFactorial(mid) < n)  ` `            ``low = mid + 1;  ` ` `  `        ``else` `            ``hi = mid - 1;  ` `    ``}  ` `    ``return` `low;  ` `}  ` ` `  `// Driver Code  ` `static` `public` `void` `Main () ` `{ ` `    ``Console.WriteLine(findNum(1));  ` `    ``Console.WriteLine(findNum(2));  ` `    ``Console.WriteLine(findNum(5));  ` `    ``Console.WriteLine(findNum(24));  ` `    ``Console.WriteLine(findNum(100));  ` `    ``Console.WriteLine(findNum(1221));  ` `}  ` `}  ` ` `  `// This code is contributed by akt_mit  `

## PHP

 `= ``\$n` `&& ` `            ``findDigitsInFactorial(``\$mid` `- 1) < ``\$n``) ` `            ``return` `(int)``round``(``\$mid``); ` ` `  `        ``else` `if` `(findDigitsInFactorial(``\$mid``) < ``\$n``) ` `            ``\$low` `= ``\$mid` `+ 1; ` ` `  `        ``else` `            ``\$hi` `= ``\$mid` `- 1; ` `    ``} ` `    ``return` `(int)``round``(``\$low``); ` `} ` ` `  `// Driver Code ` `echo` `findNum(1) . ````" "````; ` `echo` `findNum(2) . ````" "````; ` `echo` `findNum(5) . ````" "````; ` `echo` `findNum(24) . ````" "````; ` `echo` `findNum(100) . ````" "````; ` `echo` `findNum(1221) . ````" "````; ` ` `  `// This code is contributed by mits ` `?> `

Output:

```0
4
8
24
70
532
```

Complexity Analysis
The complexity for the binary search is O(log(2*n)), if we ignore the complexity of the logarithmic function. Hence overall complexity is O(log(n)).