3
\$\begingroup\$

I was working with this problem, which is to find the number of zeros at the end of any factorial.

Here's my solution:

#include<bits/stdc++.h>
using namespace std;
int main(){

    int numCases,num,zeroCount=0,mulFive,temp,i=0;
    cout<<numeric_limits<int>::max()-1000000000<<endl;
    cin>>numCases;
    int solutionArray[numCases];
    temp=numCases;
    while(numCases--)
    {
         zeroCount=0;
         cin>>num;
         mulFive=5;
         while(num/mulFive!=0)
         {
             zeroCount=zeroCount+ (num/mulFive);
             mulFive=mulFive*5;
         }
         solutionArray[i]=zeroCount;
         i++;
         //cout<<zeroCount;
    }
    for(int k=0;k<temp;k++)
        cout<<solutionArray[k]<<endl;

    return 0;
}

This is the most basic code that I could come up with. How should I make it more efficient using the same logic? Perhaps I should use different logic?

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

There is a problem with your solution for large numbers ( >= 5^13 to be exact) because mulFive=mulFive*5; will go negative as the int overflows.

To protect against this, you could do

 while(num/5!=0)
 {
     zeroCount=zeroCount+ (num/5);
     num = num/5;
 }

i.e. divide the number rather than multiply the divisor, then only the size of num is a limit (2^31-1)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.