// 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...
// 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.
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
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)