You are not logged in. Please login at www.codechef.com to post your questions!

×

FCTRL - Editorial

5
8

PROBLEM LINK:

Practice

Author: ADMIN

Editorialist: SUSHANT AGARWAL

DIFFICULTY:

EASY

PREREQUISITES:

Basic looping,Basic Maths(Number Theory)

PROBLEM:

Find the Number of Trailing Zeroes at the end of N!

EXPLANATION:

Let us look at some examples and develop the algorithm step by step as we go along.

Suppose I need to find out how many times 10 is a factor in the expansion of 23!.

A number gets a zero at the end of it if the number has 10 as a factor. For instance, 10 is a factor of 50, 120, and 1234567890.Since 5×2 = 10, I need to account for all the products of 5 and 2. Looking at the factors in the expansion of a factorial, there are many more numbers that are multiples of 2 (2, 4, 6, 8, 10, 12, 14,...)than are multiples of 5 (5, 10, 15,...). That is, if I take all the numbers with 5 as a factor, I'll have way more than enough even numbers to pair with them to get factors of 10 (and another trailing zero on my factorial). So to find the number of times 10 is a factor, all I really need to worry about is how many times 5 is a factor in all of the numbers between 1 and 23. How many multiples of 5 are between 1 and 23? There is 5, 10, 15, and 20, for four multiples of 5. Paired with 2's from the even factors, this makes for four factors of 10, so:

23! has four trailing zeroes

Find the number of trailing zeroes in 101! Okay, how many multiples of 5 are there in the numbers from 1 to 101? There's 5, 10, 15, 20, 25,... Oh, heck; let's do this the short way: 100 is the closest multiple of 5 below 101, and 100 ÷ 5 = 20, so there are twenty multiples of 5 between 1 and 101.

But wait: 25 is 5×5, so each multiple of 25 has an extra factor of 5 that I need to account for. How many multiples of 25 are between 1 and 101? Since 100 ÷ 25 = 4, there are four multiples of 25 between 1 and 101.

Adding these, I get 20 + 4 = 24 trailing zeroes in 101!

Find the number of trailing zeroes in the expansion of 1000! Okay, there are 1000 ÷ 5 = 200 multiples of 5 between 1 and 1000. The next power of 5, namely 25, has 1000 ÷ 25 = 40 multiples between 1 and 1000. The next power of 5, namely 125, will also fit in the expansion, and has 1000 ÷ 125 = 8 multiples between 1 and 1000. The next power of 5, namely 625, also fits in the expansion, and has 1000 ÷ 625 = 1.6.625 has 1 multiple between 1 and 1000. (I don't care about the 0.6 "multiples", only the one full multiple, so I truncate my division down to a whole number.) In total, I have 200 + 40 + 8 + 1 = 249 copies of the factor 5 in the expansion, and thus: 249 trailing zeroes in the expansion of 1000!

The General Algorithm to be followed is given below:

  • Take the number that you've been given the factorial of.
  • Divide by 5; if you get a decimal, truncate to a whole number.
  • Divide by 5^2 = 25; if you get a decimal, truncate to a whole number.
  • Divide by 5^3 = 125; if you get a decimal, truncate to a whole number.
  • Continue with ever-higher powers of 5, until your division results in a number less than 1. Once the division is less than 1, stop.
  • Sum all the whole numbers you got in your divisions. This is the number of trailing zeroes.

Here's how the algorithm works. How many trailing zeroes would be found in 4617!, upon expansion? I'll apply the procedure from above:

  • 5^1 : 4617 ÷ 5 = 923.4, so I get 923 factors of 5
  • 5^2 : 4617 ÷ 25 = 184.68, so I get 184 additional factors of 5
  • 5^3 : 4617 ÷ 125 = 36.936, so I get 36 additional factors of 5
  • 5^4 : 4617 ÷ 625 = 7.3872, so I get 7 additional factors of 5
  • 5^5 : 4617 ÷ 3125 = 1.47744, so I get 1 more factor of 5
  • 5^6 : 4617 ÷ 15625 = 0.295488, which is less than 1, so I stop here.
  • Then 4617! has 923 + 184 + 36 + 7 + 1 = 1151 trailing zeroes.

EDITORIALIST'S SOLUTION:

Editorialist's solution can be found here.

This question is marked "community wiki".

asked 17 Dec '14, 13:55

sushant96's gravatar image

0★sushant96
21368
accept rate: 0%

edited 17 Dec '14, 13:59


include <iostream>

#include <cstdio>
using namespace std;

int main()
{
int t;
cin >> t;

for (int k = 0; k < t; k++)
{
int n;
scanf("%d", &n);

int c = 0;
while (n >= 5)
{
n /= 5;
c += n;
}

printf("%d\n", c);
}

return 0;
}
link

answered 05 Apr '15, 15:24

vaishnavi_v's gravatar image

0★vaishnavi_v
1
accept rate: 0%

There is a bit simpler solution to this problem.

  1. start with the number n you've been given the factorial of
  2. divide n by 5. truncate the result tmp to a whole number and save it as a variable trailingZeros
  3. divide tmp by 5. truncate the result to a whole number and add it to trailingZeros
  4. ... repeat until result < 1
  5. the sum trailingZeros is the number of trailing zeros in n

Example:

int getTrailingZeros(int n) {
  int trailingZeros = 0;
  int tmp;
  while ((tmp = n / 5) >= 1) {
    trailingZeros+=tmp;
    n = tmp;
  }
  return trailingZeros;
}

See also here.

link

answered 21 Jun '15, 21:12

ng_agi's gravatar image

0★ng_agi
11
accept rate: 0%

edited 21 Jun '15, 21:15

Python:

def z(n):
    zeros=0
    i=1
    while n//5**i>0:
        zeros=zeros+n//5**i
        i=i+1
    return zeros
t=int(input())
while t>0:
    n=int(input())
    print(z(n))
    t=t-1
link

answered 31 Dec '15, 16:51

rkking's gravatar image

2★rkking
1
accept rate: 0%

include<stdio.h>

int main() { long long int j, a, i, z,T,N,count;

scanf("%lld",&T); for(i=0;i<T;i++) { scanf("%lld",&N); count=0; for(j=1;j<=N;j++) { a=j; if(a%5==0) while(a) { if(a%5==0) count++; a=a/5;

    }

} printf("%lld\n",count); }

return 0;

i want to ask why isnt it working ?

link
This answer is marked "community wiki".

answered 19 May '16, 22:42

sreejadeb1997's gravatar image

2★sreejadeb1997
1
accept rate: 0%

include <stdio.h>

include <math.h>

include <stdlib.h>

main(){ int i=0,j,l,a,b; scanf("%d",&j); for(i=0;i<j;i=i+1){ scanf("%d",&l); a=fact(l); b=cntz(a);

printf("%d\n",b); } } /----- For the Factorial-----/ int fact(int n){ int m=0,facto=1; for(m=n;m>0;m--){ facto=facto*m; } return(facto);

}

/------For Counting Zeros-----/ int cntz(int x){ int y=0,z; while(z==0){ z=x%10; if(z==0){ y=y+1; x=x/10;}

    }
    return(y);

}
link

answered 30 May '16, 17:49

pratham_shanu's gravatar image

0★pratham_shanu
1
accept rate: 0%

can anyone tell me whats wrong in this code? thank you

include <iostream>

include<math.h>

using namespace std;

int main() { int n,a,ans=0; cin>>n; while(n!=0) { cin>>a; for(int i=1;pow(5,i)<a;++i) { ans=ans+(a/pow(5,i)); } cout<<ans<<"\n"; ans=0; n--; } }

the code gave me exact answer as given in example in IDE, but showed me wrong after submission.

link

answered 30 Jul '16, 19:31

abirbandy's gravatar image

0★abirbandy
11
accept rate: 0%

edited 30 Jul '16, 19:34

WHY IS THIS ANSWER WRONG ?

include <stdio.h>

include <math.h>

main() { int s,x,i,n; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&x); s=x/5+x/25+x/125+x/625+x/3125+x/15625+x/pow(5,7)+x/pow(5,8)+x/pow(5,9)+x/pow(5,10)+x/pow(5,11)+x/pow(5,12)+x/pow(5,13); printf("%d\n",s); } return 0; }

link

answered 26 Aug '16, 14:05

generico21's gravatar image

4★generico21
1
accept rate: 0%

Hello I am doing it with python. All of test cases are passing but My solution is not accepted .Can someone help please. Here is my code :

  def fact(x):
    count=0
    while x/5>0:
        count+=x/5
        x=x/5
    #print("hello")
    print (count)
t=int(input())

for i in range(t):
    fact(int(input()))
link

answered 30 Sep '16, 20:41

vishwas22's gravatar image

0★vishwas22
11
accept rate: 0%

edited 30 Sep '16, 20:43

import java.util.; import java.io.;

public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int noftimes=sc.nextInt(); for (int i = 0; i < noftimes; i++) { int value=sc.nextInt(); int count=getValue(value/5); System.out.println(String.valueOf(count));
}

} private static int getValue(int n) { if (n <= 5) { return n; } return getValue(n / 5) + n; } }

link

answered 28 Jan '17, 17:27

mkgarg99's gravatar image

0★mkgarg99
1
accept rate: 0%

#include<stdio.h> int main() { unsigned n, mul; unsigned t=0,i,z=0,temp,c2=0,c5=0; scanf ( "%u", &t ); while ( t-- ) { c5=0; c2=0; scanf ( "%u", &n ); for ( i = 1 ;i <= n ; i++){ mul *= i; temp = i; while ( temp % 5 == 0 && temp > 0){ c5++; temp = temp / 5 ; } while ( temp % 2 == 0 && temp > 0){ c2++; temp = temp / 2 ; } } printf("%u\n",c5); } return 0; }

why is this not running in console? why are judges facing infiniteloop here.

link

answered 10 Mar '17, 22:15

abhinav00719's gravatar image

2★abhinav00719
1
accept rate: 0%

include<stdio.h>

int fact(int); int zeroes(int); main() { int p,i,j,a,b; printf("enter the number of numbers to be entered");scanf("%d",&p); for(i=0;i<p;i++){scanf("%d",&j);a=fact(j);b=zeroes(a);printf("%d",b);}} int fact(int j) {int f;if(n==1)f=1;else f=f*fact(j-1);return f;} int zeroes(int a); {int y=0,z;while(z==0){z=a%10;if(z==0){y=y+1;a=a%10}}return y;}

link
This answer is marked "community wiki".

answered 13 May '17, 23:08

vaishnavi6799's gravatar image

0★vaishnavi6799
1
accept rate: 0%

include<stdio.h>

int fact(int); int zeroes(int); main() { int p,i,j,a,b; printf("enter the number of numbers to be entered");scanf("%d",&p); for(i=0;i<p;i++){scanf("%d",&j);a=fact(j);b=zeroes(a);printf("%d",b);}} int fact(int j) {int f;if(n==1)f=1;else f=f*fact(j-1);return f;} int zeroes(int a); {int y=0,z;while(z==0){z=a%10;if(z==0){y=y+1;a=a%10}}return y;}

link
This answer is marked "community wiki".

answered 13 May '17, 23:09

vaishnavi6799's gravatar image

0★vaishnavi6799
1
accept rate: 0%

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned long long int t, n, i, maxpo, sum;
cin>>t;
while(t--)
{
    cin>>n;
    maxpo = sum = 0;
    maxpo = (int)(log(n)/log(5));
    for(i = 1;i <= maxpo;i++)
        sum += n/pow(5,i);
    cout<<sum<<endl;
}
}
link

answered 14 May '17, 21:36

sidharth14163's gravatar image

2★sidharth14163
111
accept rate: 0%

edited 14 May '17, 21:37

instead of finding the factors why can't we actually count the no of zero's of that number using "number modulo 10" which gives us the last digit in that number

link

answered 28 May '17, 23:58

vercetti's gravatar image

0★vercetti
1
accept rate: 0%

can we solve this by actually counting the trailing zero's and not by the factor method? Won't that be much simpler?

link

answered 29 May '17, 00:02

vercetti's gravatar image

0★vercetti
1
accept rate: 0%

include<stdio.h>

int calc (int entr); int main(void) { long num; scanf("%ld",&num); long entr[num]; long fact[num]; for(int i=0;i<num;i++) { scanf("%ld",&entr[i]); fact[i]=calc(entr[i]);

}
for(int i=0;i<num;i++)
    printf("%ld\n",fact[i]);
return 0;

} int calc (int entr) { int fin= entr/5; if(fin==0) return 0; else return fin+calc(fin);

}

link

answered 14 Jul '17, 08:34

ayushjain1144's gravatar image

2★ayushjain1144
1
accept rate: 0%

include<stdio.h>

int calc (int entr); int main(void) { long num; scanf("%ld",&num); long entr[num]; long fact[num]; for(int i=0;i<num;i++) { scanf("%ld",&entr[i]); fact[i]=calc(entr[i]);

}
for(int i=0;i<num;i++)
    printf("%ld\n",fact[i]);
return 0;

} int calc (int entr) { int fin= entr/5; if(fin==0) return 0; else return fin+calc(fin);

}

link
This answer is marked "community wiki".

answered 14 Jul '17, 08:37

ayushjain1144's gravatar image

2★ayushjain1144
1
accept rate: 0%

include<stdio.h>

include<math.h>

long int zeroes(long int a); int main() { int n,i=0; long int k[100000]; scanf("%d",&n); for(i=0;i<n;i++) {="" scanf("%ld\\n",&k[i]);="" }="" for(i="0;i&lt;n;i++)" {="" zeroes(k[i]);="" }="" return="" 0;="" }="" long="" int="" zeroes(long="" int="" a)="" {="" int="" z="1,b=0,i=0;" while(a="">5*z) { z=pow(5,i+1); b+=a/z; i+=1; } printf("%ld\n",b); }

why wrong?

link

answered 03 Sep '17, 14:30

niksrocks123's gravatar image

2★niksrocks123
11
accept rate: 0%

include<iostream>

using namespace std; int main() {int x,t,i; cin>>t; if(t<=10000) {for(int j=0;j<t;j++) {int="" count="0;" cin="">>x; if(x<=1000000000 && x>=1) {for(i=5;x/i>=1;i=i*5) {count=count+(x/i);} cout<<count<<"\n";} else break; }}

}

link

answered 10 Sep '17, 21:04

tushar_1999's gravatar image

1★tushar_1999
1
accept rate: 0%

Could someone please tell me what is wrong with this code. Basic idea behind my logic is i calculate the factorial by multiplying all numbers from 1 to N(N being the number itself) and at each juncture i check the condition whether the factorial at that particular instant is divisible by 10 leaving a remainder of 0 and if it is i am calculalating the sum at the end. here goes the code.

include <iostream>

using namespace std;

int main() { int a,b,c,fact=1,sum=0,e=0; cin>>a;//for taking in the total number of input int f=0; for(b=0;b<a;b++) {="" cin="">>c;//selecting each input value

for(int d=1;d<=c;d++)
{f=0;
    fact=fact*d;
    e=fact;
    while(f==0)
    {
    if(fact%10==0)
    {
        sum++;
        fact=fact/10;
        f=0;
    }
    else{f=1;}}
    fact=e;
}
cout<<sum<<endl;
sum=0;
fact=1;}}
link

answered 09 Nov '17, 00:37

dark_pharoah's gravatar image

2★dark_pharoah
1
accept rate: 0%

@dark_pharoah Your logic is correct but it takes more time, quite cumbersome and is prone to mistakes. The logic is 0's are formed by combination of 5's and 2's(since 5x2=10) Agree? For example 30=2x3x5(0 is formed by 5 and 2). So, we have to find min(number of 2's,number of 5's) in n! so that they can combine to form 0's. That can be found by:-

number of 2's->[n/2]+[n/2^2]+.... until it is 0

number of 5's->[n/5]+[n/5^2]+..... until it is 0, Here [] is floor

The reason for this is explained clearly in the above editorial. Have a look at it.

We can observe that number of 5's will be less as it's a big number(so just calculate number of 5's)

So, the code goes as follows:- Click Here

link

answered 09 Nov '17, 02:48

ramini's gravatar image

2★ramini
615
accept rate: 8%

edited 09 Nov '17, 03:00

include<iostream>

using namespace std;

int mmofive( long int t) { int n=0, pof=5; while ( t/pof>0) {pof*=5; n++;} return n-1; }//max divisible multiple of 5 (power)

int main() { long int n,t; int i,j; int trailingzero=0; cin>>n;

const long int f=n; int A[f]; for ( i=0; i<n; i++)="" {cin="">>t; for(j=5;j<=5^mmofive(t);j*=5) {trailingzero+=t/j;} A[i]=trailingzero; trialingzero=0; }

for (long int i=0; i<n; i++) {cout<<A[i]<<endl;}

return 0; }

WHY NOT WORKING? :(( i devised the same logic as expected. but it says it exceeds time limit. i believe, even if the number is as large as 100000000 , on dividing by 5 continuously, the final output should take quite less time.

link

answered 13 Nov '17, 17:29

palaash's gravatar image

0★palaash
1
accept rate: 0%

include <stdio.h>

int main() { int n = 4617, troll = 0, i=1, num = 5,quotient;

while(quotient > 1)
{
    i = num * i;
    //printf("%d",i);
    quotient = n/i;
    troll = troll + quotient;
}
printf("%d\n",troll);

return 0;

}

link

answered 19 Aug '18, 17:53

sumitsingh34's gravatar image

0★sumitsingh34
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×3,764
×631
×167

question asked: 17 Dec '14, 13:55

question was seen: 17,073 times

last updated: 10 Feb, 12:29