Problem Code: FCTRL
Factorial
My code failed to pass this test case …when n = 8735373
#include<bits/stdc++.h>
using namespace std;
int multiply(int size,int *arr,int n)
{
int carry = 0;
for(int x=0;x<size;x++)
{
int prod = (arr[x] * n) + carry;
arr[x] = prod % 10;
carry = prod / 10;
}
while(carry)
{
arr[size] = carry % 10;
carry = carry / 10;
size++;
}
return size;
}
int main()
{
int t;
cin>>t;
while(t–)
{
long long n;
cin>>n;
int *arr;
arr = new int[1000000];
arr[0] = 1;
int size = 1;
for(int i=2;i<=n;i++)
{
size = multiply(size,arr,i);
}
for(int i=0;i<size;i++)
{
if(arr[i] != 0)
{
cout<<i<<endl;
break;
}
}
delete []arr;
}
}
For every test case, you are doing a lot of operations.
N is very large and a loop of size N will break even for 1 test case, let alone 100,000 cases.
The number of zeros in factorial of a number can be computed by repeated division by 5
More formally, N(Z)=[\frac{Z}{5}]+[\frac{Z}{5^2}]+[\frac{Z}{5^3}]..... where [x] denotes the greatest integer less than or equal to x.
Why does it work?
Consider the prime factorization of any number N
N=2^{p2} * 3^{p3} *5^{p5} ...
1.Observe that the number of zeros in N must be min(p2,p5). ( Why? )
2; Also, when we are computing factorial of any number, the number of twos will be more than the number of 5s (Why?)
3. Therefore, the number of zeros in factorial of a number is the number of 5s in its factorization.
How do we calculate number of 5s?
Now, look at the above formula carefully. The first term captures all numbers divisible by 5 at least once, each of these numbers contributes 1 to p5. But there are numbers which contribute more than 1 to p5, so we have the other terms in the formula as well.
Please ask if something is not clear about the algorithm. I will leave the implementation to you
1 Like