Monday, 19 September 2011

Factorial of a large number

To calculate factorial for a big number we need to use integer array as factrial value wont fit in the
size of the integer.

Ex:
2432902008176640000 = 20!
51090942171709440000 = 21!
8222838654177922817725562880000000 = 31!
263130836933693530167218012160000000 = 32
295232799039604140847618609643520000000 = 34!

Create and integer array  and initialize with 0.  In every iteration stored value(val) is multiplied and val%10 value will be stored in current index and val/10 will be added ( carry forwarded) to next number.Here multiplier will be incremented by one for each iteration
ex:
   5! = 120;
   a = {0,0,0,0,0};
   i=1;
  a = {1,0, 0,0,0};
  i=2;
  a = {2,0,0,0,0};
  i=3;
  a= {6,0,0,0,0};
  i=4;
  a={4,2,0,0,0};
  i=5;
  a={0,2,1,0,0}
  reverse array and print output.
code
-------


#include <iostream>
using namespace std;

int main()
{
   int a[200]={0};
   //100 factorial 
   int carry=1,m=1,n=100,j,val,i;
   for(i=1;i<=n;i++)
   {
      j=0;
      while( j < m || carry !=0 )
      {
          val = a[j]*i + carry;
          a[j] = val % 10;
          carry = val/10;
          j++;
      }
      m = j;
   }
   
    for(i=m-1;i>=0;i--)
      cout<<a[i];
}

Thursday, 8 September 2011

Serialize and deserialize a binary tree

Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.To serialize a binary tree  we need to store information  of inorder and one of preoder/postorder traversals in arrays and transfer the data . De-serialization can be done using inorder and preorder data. If the tree is a Binary Search Tree then we  need only  preorder /postorder.

Following is the code to create a binary tree from inorder and preorder traversals.I have not tested it, there may be typos.

struct TreeNode
{
  struct TreeNode* left;
  struct TreeNode* right;
  int  elem;
};
TreeNode* BinaryTreeFromOrderings(int* inorder, int* preorder, int length)
{
  if(length == 0)
    {
      return NULL;
    }
  //We have root then;
  TreeNode* node = new TreeNode;
  node->elem = *inorder;
  int rootIndex = 0;
  for(;rootIndex < length; rootIndex++)
    {
      if(inorder[rootIndex] == *inorder)
        {
           break;
        }
    }
  //Left
  node->left = BinaryTreeFromOrderings(inorder+1, preorder, rootIndex);
  //Right
  node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
  return node;
}





Implement N stacks using one array

I have not compiled or tested the below code :-)

template<typename T> class MultiStack {
public:
  MultiStack(int arraySize, int numberOfStacks);
  ~MultiStack();

  void Push(const T & x, int i);

  T Pop(int i);

private:
  struct Node {
    T data
    Node * prev;
  };

  Node * Arr;
  Node ** S;
  Node * gptr;
};

/* MultiStack Constructor */
template<typename T> MultiStack::MultiStack (int arraySize, int numberOfStacks) {
  // sanity checks
  if (arraySize < 1) throw "MultiStack: arraySize must be greater than zero";
  if (numberOfStacks < 1) throw "MultiStack: numberOfStacks must be greater than zero";

  // allocate array
  Arr = new Node[arraySize];
  // initialize free stack: each prev points to next node in array
  for(int n = 0; n < arraySize - 1; ++n) Arr[n].prev = &(Arr[n+1]);
  Arr[arraySize - 1].prev = (Node *)NULL;

  // allocate stack top pointers
  S = new Node*[numberOfStacks];
  // initialize stack top pointers to null
  for(int i = 0; i < numberOfStacks; ++i) S[i] = (Node *)NULL;

  // free stack top pointer points to first node of array
  gptr = &(Arr[0]);
}

/* MultiStack Destructor */
template<typename T> MultiStack::~MultiStack() {
  delete[] Arr; delete[] S;
}

/* MultiStack Push */
void template<typename T> MultiStack::Push (const T & x, int i) {
 
  if (i < 0 || i >= sizeof(S)/sizeof(Node *)) throw "MultiStack: Push: Invalid Stack";
  if (gptr == NULL) throw "MultiStack: Push: Array Space Exhausted";

  // pop node from free stack
  Node * temp = gptr;
  gptr = temp->prev;

  // assign value
  temp->data = x;

  // push node to given stack
  temp->prev = S[i];
  S[i] = temp;
}

/* MultiStack Pop */
T template<typename T> MultiStack::Pop (int i) {
  // sanity checks
  if (i < 0 || i >= sizeof(S)/sizeof(Node *)) throw "MultiStack: Pop: Invalid Stack";
  if (S[i] == NULL) throw "MultiStack: Pop: Pop Attempted on Empty Stack";

  // pop node from given stack
  Node * temp = S[i];
  S[i] = temp->prev;

  // push node to free stack
  temp->prev = gptr;
  gptr = temp;
}