Count total zeroes in N! (not trailing zeroes )

help
,
1

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

link : CodeChef: Practical coding for everyone

Edit : @admin Please unlock the solutions of this contest :pray:

4 Likes
3

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

4

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

6

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'))
7

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

8

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!

9

then it must show TLE why WA

10

image
int cant store such a huge value?

11

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

12

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
13

oh… i didnt know python can store big numbers.

14

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

15

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

16

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

2 Likes
17

Thanks :slight_smile:

18

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
19

LMAO :rofl: :rofl: 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;
     }
     return total;
}
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 :frowning: i think there is no algo other than brute force

20

Bhai kitne logo ko bolu ? Read question first :roll_eyes:

21

Really 0 AC!!

22

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 :frowning_face: