Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
we can easily do this using 2 extra stacks.
ReplyDeleteAre we required to do this without using any extra space?
You can use the system stack,but no external extra space.Try using recursion.
ReplyDelete// first count the no. of items.Then the idea is to store the top item in a temporary variable and then pop all the items recursively,push the stored item first and then all the items in the stack frame(recursively). Now, pop one item as it is the same as the bottommost item and decrement the counter as we have to reverse n-1 items only this time. Follow the recursive approach back again and so on...
ReplyDelete// this function counts the no. of items
int noOfItems(stack &s){
static int c=0;
if(s.isEmpty())return c;
item t=s.pop();
c++;
noOfItems(s);
s.push(t);
return c;
}
// this function fixes one item at its appropriate position in the reverse order.
void iteration(stack &s,int count,int i,int r){
static int setr=1;
setr=r;
if(i){
item fix=s.pop(); //assuming that s.pop() returns //the item popped
s.push(fix);
i=0;
}
if(count){
item t=s.pop();
iteration(s,count-1,0,1);
if(setr){
s.push(fix)
setr=0;
}
s.push(t);
}
}
void reverse(stack &s){
static int c=noOfItems(&s);
while(c--){
iteration(s,c+1,1,1);
s.pop();
}
}
the above approach takes O(n^2) with space complexity of O(n). can we do better?
ReplyDelete1. Have a utility function , which initially passes the source stack and an empty destination stack.
ReplyDelete2. At each stage , pop the element from the source and push it into destination. The point to note, pass the reference during the recursion.
3. Each the source is empty , assign the source label to the destination and return.
Space Complexity : O(1)
Time Complexity : O(n)