# Count total zeroes in N! (not trailing zeroes )

Given N ( N < 105 ) , Find all zeroes in N !

Ex :

N = 6 => N! = 720 , , Total zero = 1

N = 18 => N! = 6402373705728000 , , Total zero = 5

N = 59 , , Total zero = 19

How can i solve this ? @galencolin @hetp111 @nuttela @nishant403 @everule1 @saurabhshadow

4 Likes

LMAO … . . If i want this then I’m not asking here …Plzz read question first

for N = 18 => N / 5 + N / 25 = 18 /5 + 18 / 25 = 3+0 = 3
but total zeroes are 4

even brute force python shows WA … why ?

``````while(True):
try:
n = int(input())
except:
break;
x = 1
for i in range(1,n+1):
x = x*i
print(str(x).count('0'))
``````

For N = 10^5
N! will be a very huge number

I think you should find no of zeroes at each step and store them. Now you can access the value in O(1). But in ques max value of n should be given.
Like for(i=1 -> n)
at each i it will give i!

then it must show TLE why WA

int cant store such a huge value?

kya baate kr rha hai yrr…python h bhai dekh to

How did you conclude that N can be that large (10⁵)? I don’t see any constraints… BTW i also tried bruteforce but WA😑

1 Like

oh… i didnt know python can store big numbers.

I assume as many solutions passed the test case means solution exists …that’s why i asked @admin plz unlock the solutions

did you try custom inputs to see if it is working correctly. Try with 1 and also with a very big number.

Done. Though the problem looks very shady - Proceed with caution.

2 Likes

Thanks

For getting Zeros(‘0’) the number should be multiplied by 5 and 2.
since there are so many even numbers between one and the given number, so we need to calculate the number of 5’s, 25’s, 125’s, …, 5^n’s. where 5^n<=N
the formula is N//5 + N//25 + N//125 + …+ N//(5^n)

1 Like

LMAO AC solutions given below - -

``````#include<stdio.h>

int main()
{
return 0;
}
``````
``````#include<stdio.h>

int main()
{
long int n;
int t,cur,s;

for(scanf("%d",&t);t>0;t--)
{
scanf("%ld",&n);
for(cur=5,s=0;n/cur;s+=n/cur,cur*=5);
printf("%d\n",s);
}

return 0;
}

``````
``````#include<bits/stdc++.h>
using namespace std;
#define MAX 1000
long zero(long number,long factor){
long total,deno;
if(number==5) return 1;
total=0;
deno=factor;
while(deno<number){
total+=number/deno;
deno*=factor;
}
}
int main(){
long N[MAX],c2,c1;
int i,t;

scanf("%d",&t);
for(i=0;i<t;i++)
scanf("%ld",&N[i]);
i=-1;
while(++i<t){
c1=zero(N[i],2);
c2=zero(N[i],5);
if(c1<c2) printf("%ld\n",c1);
else printf("%ld\n",c2);
}
return 0;
}

``````

all are wrong i think there is no algo other than brute force

Bhai kitne logo ko bolu ? Read question first

Really 0 AC!!

Even 6 star did this see -

``````#include <algorithm>
#include <bitset>
#include <deque>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<int,int> PI;
typedef vector<pair<int,int> > VPI;
typedef vector<string> VS;

#define ST          first
#define ND          second
#define ALL(x)      (x).begin(), (x).end()
#define FOR(i,s,n)  for(i=s;i<(n);++i)
#define LOOP(i,x)   for(i=0;i<SZ(x);++i)
#define IT(i,x)     for(typeof(x.begin()) i=x.begin();i!=x.end();++i)
#define PB          push_back
#define MP          make_pair
#define SZ(x)       (int)(x.size())
#define DISP(x)     cout << #x << ": " << x << endl;

int main()
{
ull n,m;
int t;
scanf("%d",&t);

while(t-- && (cin >> n))
{
//cin >> n;
int ans=0;
for(;n;n/=5)
{
ans+=(n/5);
}
cout << ans << endl;
}

return 0;
}

``````

Which is the code for finding trailing zeroes