O_O No idea

Hint: If a and b are two positive integers, the product a*b will have zero as the last digit if i) either a or b or both have zero as the last digit ii) if a has five as the last digit and b is even iii) if b has five as the last digit and a is even,

you loop through numbers from 1 to the one that matches, calculation the number of trailing zeros like this:
the sum of quotients of i(the variable you use in the loop) and the jth power of 5(yeah, another loop, a while, until the quotient is less than 1), and then compare it to the kth required number of trailing zeros from zero.in. the only problem is to find a way to know when there is no number withthat number of trailing zeros.

Hint2: In the sequence [1, 2, 3, ...., N-1, N], the number of integers ending in the digit five is:
( N/5 + 1 ) / 2 (integer division)

Oh thanks :) I think I can try to solve it now :)

EDIT: Thanks a lot. Hint 2 was helpful. +rep JLBorges.

Last edited on

PM from jumper007:

..., but how did you find this recursion ?

Hint2: In the sequence [1, 2, 3, ...., N-1, N], the number of integers ending in the digit five is:
( N/5 + 1 ) / 2 (integer division)

a. In the sequence, the number of integers divisible by five is N/5

b. Half these integers end in the digit five, half end in digit zero.

c. Multiples of five are 5,10,15,20,25,... The number of these multiples ending in five is either equal to or one greater than those ending in zero

d. ergo: ( N/5 + 1 ) / 2

I have a problem. Your formula does not give the right answers for all integers.
Your formula: ((N/5)+1)/2 = Xi => N = ((2*Xi)-1)*5
Let Xi be 2
N = ((2*2)-1)*5 = (4-1)*5 = 3*5 = 15
But the good answer is 10. (10! = 3 680 800)... :|

Last edited on

N = 10 * Xi - 5 ... which is not actually true...

Last edited on

Integer division! 11/3 == 3. So is 3*3 == 11?

( 15/5 + 1 ) / 2 == 2
( 16/5 + 1 ) / 2 == 2
( 17/5 + 1 ) / 2 == 2
( 18/5 + 1 ) / 2 == 2
( 19/5 + 1 ) / 2 == 2
( 20/5 + 1 ) / 2 == 2
( 21/5 + 1 ) / 2 == 2
( 22/5 + 1 ) / 2 == 2
( 23/5 + 1 ) / 2 == 2
( 25/5 + 1 ) / 2 == 2

All these result in 2 ( the two integers are 5 and 15)

Misunderstanding... I checked a google dictionary now. I didn't know what an Integer Division is. Sorry.

Anyway, can you tell me how to write that in the code so it can actually run ? I have to hurry...

EDIT: Ermm excuse me but

( 25/5 + 1 ) / 2 == 2

actually is = 3 .... But not this is the problem now... maybe you wanted to say 24.

Thanks in advance.

Last edited on

> maybe you wanted to say 24

Yup. Typo!

> Anyway, can you tell me how to write that in the code so it can actually run ? I have to hurry...

It is your homework; unless you do it yourself, you won't be learning anything.

Make an earnest attempt to write the program. If despite your best efforts you are unable to make progress, post a specific question here and people would be willing to help you out.

1) It is not homework.
2) I am doing this EXTRA-school.
3) Its an Olympiad exercise.
4) I did write the program with no success. I AM NO GOOD AT MATH -.-

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

int main()
{	
	int T,i,N,Xi;
	
	ifstream inFisier("zero.in");
	ofstream outFisier("zero.out");
	
	if (!inFisier.is_open() || !outFisier.is_open())
	{
		cout << "Error 404: File not found (or open). Please check the program files.";
		return 1;
	}
	else
	{
		inFisier >> T;
		
		for (i = 1; i <= T; ++i)
		{
			inFisier >> Xi;
			
			N = (2*Xi-1)*5;
			
			//if () I have no freaking idea how to ask the compiler to check if N is NOT INTEGER!!! Eg: 9/5.
			//	outFisier << "-1" << "\n";
			//else
			outFisier << N << "\n";
		}
	}
	
	inFisier.close();
	outFisier.close();
	return 0;
}

Ok. Here is a function that returns the count of trailing zeroes in the factorial of a number. What you need is the inverse of this function - where the the count of trailing zeroes is the input.

And you are not going to get any more spoon-feeding from me.

#include <iostream>

int num_zeroes( int n ) // number of trailing zeroes in n!
{
    int num_zeroes = 0 ;
    while( n ) { num_zeroes += n/5 ; n /= 5 ; }
    return num_zeroes ;
}

int main()
{
    for( int n = 5 ; n < 1001 ; n += 5 )
       std::cout << n << "! to " << n+4 << "! has "
                 << num_zeroes(n) << " trailing zeroes.\n" ;
}

here:

#include <iostream>
#include <cstdlib>
using namespace std;
int num_zeroes( int n ) // number of trailing zeroes in n!
{
    int zeroes = 0 ;
    while( n ) { zeroes += n/5 ; n /= 5 ; }
    return zeroes ;
}

int main()
{
    int i=1, n;
    cin>>n;
    while (num_zeroes(i)!=n)
    {
          i++;
          }
    cout<<i;
    system ("pause");
    return 0;
}

this works in most cases, BUT, there IS a number n for wich there is nop number x that x! has n trailing zeroes! how tu calculate that? for now i found that those numbers are 5, 11, 17, and who know wich more

WAIT! I just found the solution! all the numbers for wich there is no number that has that many trailing zeroes satisfies the equation ((n-5)%6)=0!!! That means that this is the whole complete working code wich will do exatly like the task asks;

#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int num_zeroes( int n ) // number of trailing zeroes in n!
{
    int zeroes = 0 ;
    while( n ) { zeroes += n/5 ; n /= 5 ; }
    return zeroes ;
}

int main()
{
    int i, n, m, j;
    ifstream fin ("zero.in");
    ofstream fout ("zero.out");
    fin>>n;
    for (i=0; i<n; i++)
    {
        fin>>m;
        if (!((n-5)%6))
        {
           fout<<"-1";
           continue;
           }
        j=1;
        while (num_zeroes(i)!=n)
        {
              i++;
              }
        fout<<i;
        if (i<n-1) fout<<endl;
        }
    system ("pause");
    return 0;
}

there!!!

> there IS a number n for wich there is nop number x that x! has n trailing zeroes! how tu calculate that?

Hint: Run the program that I posted earlier an examine the output a little more closely.

Look at the number of trailing zeroes for following transitions:
24! to 25!, 49! to 50! etc. (multiples of 25)
124! to 125!, 249! to 250! etc. (multiples of 125)
624! to 625!

What do 25, 125 and 625 have in common?

> What do 25, 125 and 625 have in common?

I found that yesterday... I tryed to make a function to determine whether a number in the factorial is a power of 5 or not. Anyway I couldnt make it.

I will try running your code. Thanks a lot.
I will examine both of them in detail. I need to understand it :>

Anyhow, I'm not asking for anymore

spoon feeding

but I have no idea how to invert the function...

#include <iostream>

int num_zeroes( int n ) // number of trailing zeroes in n!
{
    int num_zeroes = 0 ;
    while( n ) { num_zeroes += n/5 ; n /= 5 ; }
    return num_zeroes ;
}

int main()
{
    for( int n = 5 ; n < 1001 ; n += 5 )
       std::cout << n << "! to " << n+4 << "! has "
                 << num_zeroes(n) << " trailing zeroes.\n" ;
}

Does "n" represent the FACTORIAL ? I can't figure it out...

So, what does "n" represent ?

EDIT: Nevermind. I think I got it... I should start doing other kind of ex. which are not so complicated. Thanks for the help, but I still can't solve it. I'm not that good as I thought.

PS: I could NEVER EVER understand functions >.> (and still can't)
PS2: Sorry for wasting your time, thanks you all for the help, but it seems that I cannot understand this exercise. It's just too complicated to me ( both math and c++).

Last edited on

NO! don't close the topic! we already have the code for 5, we JUST need to upgrade it to all powers of 5 and then voila! Ana can have her questions answered! Just give us some more time!
btw, n is the nomber from wich we look for the number of trailing zeros in the factorial.
and to invert the function, I already did that in my 2 earlier posts! look at it, see if you understand.

Last edited on