Given an integer n (can be very large), 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
Examples:
Input : n = 1 Output : 1 1! = 1, hence number of digits is 1 Input : 5 Output : 3 5! = 120, i.e., 3 digits Input : 10 Output : 7 10! = 3628800, i.e., 7 digits Input : 50000000 Output : 363233781 Input : 1000000000 Output : 8565705523
We’ve already discussed the solution for small values of n in the Count digits in a factorial | Set 1. However that solution would not be able to handle cases where n >10^6
So, can we improve our solution ?
Yes ! we can.
We can use Kamenetsky’s formula to find our answer !
It 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
And that’s it !
Our solution can handle very large inputs that can be accommodated in a 32 bit integer,
and even beyond that ! .
Below is the implementation of above idea :
C++
// A optimised program to find the // number of digits in a factorial #include <bits/stdc++.h> using namespace std; // Returns the number of digits present // in n! Since the result can be large // long long is used as return type long long findDigits( 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; } // Driver Code int main() { cout << findDigits(1) << endl; cout << findDigits(50000000) << endl; cout << findDigits(1000000000) << endl; cout << findDigits(120) << endl; return 0; } |
Java
// An optimised java program to find the // number of digits in a factorial import java.io.*; import java.util.*; class GFG { public static double M_E = 2.71828182845904523536 ; public static double M_PI = 3.141592654 ; // Function returns the number of // digits present in n! since the // result can be large, long long // is used as return type static long findDigits( 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 / M_E) + Math.log10( 2 * M_PI * n) / 2.0 ); return ( long )Math.floor(x) + 1 ; } // Driver Code public static void main(String[] args) { System.out.println(findDigits( 1 )); System.out.println(findDigits( 50000000 )); System.out.println(findDigits( 1000000000 )); System.out.println(findDigits( 120 )); } } // This code is contributed by Pramod Kumar. |
Python3
# A optimised Python3 program to find # the number of digits in a factorial import math # Returns the number of digits present # in n! Since the result can be large # long long is used as return type def findDigits(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 x = ((n * math.log10(n / math.e) + math.log10( 2 * math.pi * n) / 2.0 )); return math.floor(x) + 1 ; # Driver Code print (findDigits( 1 )); print (findDigits( 50000000 )); print (findDigits( 1000000000 )); print (findDigits( 120 )); # This code is contributed by mits |
C#
// An optimised C# program to find the // number of digits in a factorial. using System; class GFG { public static double M_E = 2.71828182845904523536; public static double M_PI = 3.141592654; // Function returns the number of // digits present in n! since the // result can be large, long long // is used as return type static long findDigits( 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 / M_E) + Math.Log10(2 * M_PI * n) / 2.0); return ( long )Math.Floor(x) + 1; } // Driver Code public static void Main() { Console.WriteLine(findDigits(1)); Console.WriteLine(findDigits(50000000)); Console.WriteLine(findDigits(1000000000)); Console.Write(findDigits(120)); } } // This code is contributed by Nitin Mittal |
PHP
<?php // A optimised PHP program to find the // number of digits in a factorial // Returns the number of digits present // in n! Since the result can be large // long long is used as return type function findDigits( $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 $x = (( $n * log10( $n / M_E) + log10(2 * M_PI * $n ) / 2.0)); return floor ( $x ) + 1; } // Driver Code echo findDigits(1). "
" ; echo findDigits(50000000). "
" ; echo findDigits(1000000000). "
" ; echo findDigits(120) ; // This code is contributed by nitin mittal ?> |
Output:
1 363233781 8565705523 199
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments