Code for calculating number of trailing zeroes after factorial

Question

While trying my hands at the beginner codechef problem I came across this . So basically doing that problem with Dynamic programming is an overkill but why not try that and get some DP practice.

Nice, I almost solved that problem in minutes but the problem is this takes too much memory , and ends up with a Segmentation Fault upon entering a big integer , I solved this problem by running a ulimit -s unlimited in my local machine but that wont make the codechef judge happy.

Here is the code:

#include <iostream>
#include <vector>
#include <algorithm>
int getZeroes(long long n){
 if(n>0){
 if(n%5 == 0){
 long long a = n/5;
 int b = 1;
 while(a/5){
 if(a%5 == 0){
 b++;
 }else{
 break;
 }
 a = a/5;
 }
 return (b+getZeroes(n-1));
 }else{
 return (getZeroes(n-1));
 }
 }
}
int main(){
 int n;
 std::cin >> n;
 std::vector<int> x;
 for(int i=0;i<n;i++){
 long long cases;
 std::cin >> cases;
 x.push_back(getZeroes(cases));
 }
 for(int itr : x){
 std::cout << itr << std::endl;
 }
return 0;
}

Upon some research I found most recommend to declare the items in a heap rather than stack , but that's somewhat confusing to me. Can anyone help me to find out what can I do to overcome this?

• Loki Astari: This is a common class of problem. You need to convert the recursive call down into a loop that loops up from zero towards your number. Extra points for not forgetting numbers.
• Jerry Coffin: while (a%5) basically means while (a%5 != 0). Immediately inside that, you have if (a%5 ==0) ... else break; which (at least at first glance) makes it appear that either the loop is skipped entirely, or else the loop will break on its first iteration; either way, it appears to do nothing. A quick check on 5 (the first factorial that gives a trailing 0) shows that it produces an output of 2 (when the output should be 1).
• Jerry Coffin: An input of 3 also produces an output of 1 (but 3! is 6, so the output should be 0).
• hellozee: ehh @JerryCoffin you are wrong it doesnt produce an output of 2 on giving 5, it works fine just I need to take care of that segmentation fault.
• Jerry Coffin: Looking more carefully, I think it is a bug in your code. The problem is that you don't define what getZeroes will return for an input of 0. On this particular compiler, it apparently returns 1, but you're depending on it returning 0.

Answer 1

Code Review

All return paths from a function must return value. Leaving a function that has a non void type without a return is undefined behavior (google nasal dragons).

int getZeroes(long long n){
 if(n>0){
 // STUFF
 return stuff;
 }
 // BUT HERE there is no return.
 // Any negative value or zero causes undefined behavior.
}

This while loop seems overly cumbersome with a break;

 while(a%5){
 if(a%5 == 0){ // will this ever be true.
 // STUFF // Since it is just after a test that checks the opposite?
 }else{
 break;
 }
 a = a/5;
 }

This looks exactly the same both sides of the else:

 return (b+getZeroes(n-1));
 }else{
 return (getZeroes(n-1));

The only difference is b (which just needs to be made zero for the second case then) you can yank it out of the conditional.

Why store the results?

x.push_back(getZeroes(cases));

The only thing you do with them is print them. May as well just print them as you generate them!

• hellozee: a%5 that was a typo and as I come from a language like python , I am kinda new to input and output streams of c++ , thanks though.

Answer 2

Conflicting goals

So basically doing that problem with Dynamic programming is an overkill but why not try that and get some DP practice.

Nice, I almost solved that problem in minutes but the problem is this takes too much memory, [...] I solved this problem by running a ulimit -s unlimited in my local machine but that wont make the codechef judge happy.

You have two conflicting goals here:

• Solve the problem using DP, which you understand is inappropriate
• Solve the problem in a way that passes the online judge

Sometimes an approach you fancy may be suitable for an online judge, sometimes not. In this example it would be better to change the approach, as there's not much point using DP for this.

Overcomplicated logic

The implementation basically counts down from n 1 by 1, and for each number divisible by 5, it counts the number of times it can be repeatedly divided by 5. It doesn't need to be this way.

All you need is to count the number of 5s in the factors of all the numbers. That is:

• How many numbers <= n are there that are divisible by 5? -> n / 5
• How many numbers <= n are there that are divisible by 25 too? -> n / 5 / 5
• How many numbers <= n are there that are divisible by 125 too? -> n / 5 / 5 / 5
• ... and so on, until the result of / 5 is less than 5

Actually your inner while loop is very very close to the optimal solution. Note that there is no need for any modulo here. A nicely written solution is possible in 6 lines of code.

Coding style

Instead of a = a/5, you can write simpler as a /= 5.

The outer parentheses in return (getZeroes(n-1)) are redundant, it would be better to remove them.

The formatting is a bit too tight. It's recommended to add spaces around operators and keywords and in front of {. Consider this alternative writing style:

if (n % 5 == 0) {
 long long a = n / 5;
 int b = 1;
 while (a / 5) {
 if (a % 5 == 0) {
 b++;
 } else {
 break;
 }
 a /= 5;
 }
 return b + getZeroes(n - 1);
} else {
 return getZeroes(n - 1);
}

A bit more breezy and nicely readable, no? In some languages this style is the standard.

• hellozee: Thats why I said it was an overkill , but why not do some practice?
• janos: Sure, it's good to practice, but in this example these are conflicting goals. It's like wanting to implement a new search engine that's better than Google, but in 10 days. Conflicting objectives. Individually the objectives are possible, but not together at the same time.