Find the Largest Sum Path from root to leaf in a binary tree

#include<iostream>
#define SMALL -999999
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
 struct node* parent;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 new_node->parent=NULL;
 return new_node;
}
void parentfinder(node *root,node *parent)
{
    if(root)
    {
        root->parent=parent;
        parent=root;
        parentfinder(root->left,parent);
        parentfinder(root->right,parent);
    }
    return;
}
int height(struct node* root)
{
 if(root==NULL)
 {
  return 0;
 }
 else
 {
  int lheight=1+height(root->left);
  int rheight=1+height(root->right);
  return lheight>rheight?lheight:rheight;
 }
}
void levelorderprint(struct node* root,int level)
{
 if(root && level==0)
 {
  cout<<root->data<<"->";
  if(root->parent)
  {
      cout<<root->parent->data<<endl;
  }
 }
 else if(root)
 {
  levelorderprint(root->left,level-1);
  levelorderprint(root->right,level-1);
 }
}
void levelorder(struct node* root)
{
 int h=height(root);
 for(int i=0;i<h;i++)
 {
  levelorderprint(root,i);
  cout<<endl;
 }
}
struct node** summer(node *root,node **maximum,node *parent)
{
    if(root)
    {
        if(parent)
        {
            root->data=root->data+parent->data;
            if((*maximum)->data<root->data)
            {
                *maximum=root;
            }
        }
        parent=root;
        summer(root->left,maximum,parent);
        summer(root->right,maximum,parent);
    }
    return maximum;
}
int searchformax(node *root,node **max,bool *found,int A[100])
{
    static int i=0;
    if(root)
    {
        if(root==*max)
        {
            *found=true;
        }
        if(!(*found))
        {
            searchformax(root->left,max,found,A);
            if(!(*found))
            {
                searchformax(root->right,max,found,A);
            }
        }
        if(*found)
        {
            A[i]=root->data;
            i++;
        }
    }
    return i;
}
int main()
{
    struct node* root=createnode(1);
 root->left=createnode(2);
 root->right=createnode(3);
 root->left->right=createnode(4);
 root->left->left=createnode(5);
 root->right->right=createnode(-6);
 root->right->left=createnode(7);
 root->right->right->left=createnode(8);
 //root->right->right->left->left=createnode(10);
 root->right->right->right=createnode(10);
 parentfinder(root,NULL);
 levelorder(root);
 node *ptr=new struct node;
 ptr->data=SMALL;
 node **max=&ptr;
 max = summer(root,max,NULL);
 bool var=false;
 bool *found = &var;
 int A[100];
 int count=searchformax(root,max,found,A);
 for(int i=0;i<count-1;i++)
 {
     A[i]=A[i]-A[i+1];
 }
 cout<<"The path is:"<<endl;
 while(count--)
 {
     cout<<A[count]<<endl;
 }
}
Output:
1->
2->1
3->1

5->2
4->2
7->3
-6->3

8->-6
10->-6

The maximum sum path is:
1
3
7

Given two nodes of a Binary Tree, write a program to determine the shortest distance between the two nodes.

Approach:
1. Find the lowest common ancestor of the given nodes.
2. Find the distance (levels) between the lowest common ancestor and each given node separately.
3. Add the distances obtained in Step-2.

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
    if(root)
    {
        if(root==n1)
        {
            return 1;
        }
        else if(root==n2)
        {
            return 1;
        }
        else
        {
            return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
        }
    }
    else
    {
        return 0;
    }
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
    if(root)
    {
        int lf = help_anc(root->left,n1,n2);
        int rf = help_anc(root->right,n1,n2);
        if(lf==1 && rf==1)
        {
            return root;
        }
        else
        {
            node* lca = Ancestor(root->left,n1,n2);
            if(lca!=NULL)
            {
                return lca;
            }
            lca = Ancestor(root->right,n1,n2);
            return lca;
        }
    }
    else
    {
        return NULL;
    }
}

int customheight(node *root,node *n1,bool *found)
{
    int lheight=0,rheight=0;
    if(root)
    {
        if(*found==false && root==n1)
        {
            *found=true;
            return 0;
        }
        else if(*found==false)
        {
            lheight=customheight(root->left,n1,found);
            rheight=0;
            if(*found==false)
            {
                rheight=customheight(root->right,n1,found);
            }
            if(*found==true)
            {
                return lheight>rheight?1+lheight:1+rheight;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}
int distancethroughlca(node* n1,node* n2,node* lca)
{
    if(lca)
    {
        bool found=false;
        int dist1=customheight(lca,n1,&found);
        cout<<"Distance of "<<n1->data<<": "<<dist1<<endl;
        found=false;
        int dist2=customheight(lca,n2,&found);
        cout<<"Distance of "<<n2->data<<": "<<dist2<<endl;
        return dist1+dist2;
    }
    else
    {
        return 0;
    }
}

int main()
{
    struct node* root=createnode(1);
 root->left=createnode(2);
 root->right=createnode(3);
 root->left->right=createnode(4);
 root->left->left=createnode(5);
 root->right->right=createnode(6);
 root->right->left=createnode(7);
 root->right->right->left=createnode(8);
 //root->right->right->left->left=createnode(10);
 root->right->right->right=createnode(10);
 struct node* n1 = root->right->right->left;
 struct node* n2 = root->right->right->right;
 struct node* lca=Ancestor(root,n1,n2);
 if(lca)
 {
     cout<<"Least Common Ancestor: "<<lca->data<<endl;
 }
 cout<<"Total distance through LCA: "<<distancethroughlca(n1,n2,lca)<<endl;
}
Output:
Least Common Ancestor: 1
Distance of 8: 3
Distance of 4: 2
Total distance through LCA: 5

C++ program for Heapsort

#include<iostream>
#define SIZE 9
using namespace std;
void Maxheapify(int A[SIZE],int i,int heapsize)
{
    int largest=i;
    if(2*i <heapsize && A[i]<A[2*i])
    {
        largest=2*i;
    }
    if(2*i+1 <heapsize && A[largest]<A[2*i+1])
    {
        largest=2*i+1;
    }
    if(largest!=i)
    {
        int t=A[i];
        A[i]=A[largest];
        A[largest]=t;
        Maxheapify(A,largest,heapsize);
    }
}
void Buildmaxheap(int A[SIZE],int heapsize)
{
    int size=heapsize;
    for(int i=size/2;i>=0;i--)
    {
        Maxheapify(A,i,heapsize);
    }
}
void Heapsort(int A[SIZE])
{
    Buildmaxheap(A,SIZE);
    cout<<endl;
    int heapsize=SIZE;
    for(int i=SIZE-1;i>=1;i--)
    {
        int t=A[0];
        A[0]=A[i];
        A[i]=t;
        heapsize--;
        Maxheapify(A,0,heapsize);
    }
}
int main()
{
    int A[SIZE]={9,2,1,8,7,2,4,3,5};
    cout<<"The given array:\n";
    for(int i=0;i<SIZE;i++)
    {
        cout<<A[i]<<" ";
    }
    Heapsort(A);
    cout<<"The sorted array:\n";
    for(int i=0;i<SIZE;i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}

Given an array of positive integers, rearrange them so that they together form the largest number

#include<iostream>

#define SIZE 4
using namespace std;

bool decide(int a,int b)
{
    int ta=a,tb=b;
    int pa=1,pb=1;
    while(a>0)
    {
        a/=10;
        pa*=10;
    }
    while(b>0)
    {
        b/=10;
        pb*=10;
    }
    int a_b=ta*pb+tb;//Append b after a.
    int b_a=tb*pa+ta;//Append a after b.
    if(a_b>b_a)
    {
        return false;
    }
    else
    {
        return true;
    }
}

int main()
{
    int A[SIZE]={87,181,9,5};
    //Use any sorting technique but the decide function is the key.
    for(int i=0;i<SIZE;i++)
    {
        for(int j=0;j<SIZE-i-1;j++)
        {
            if(decide(A[j],A[j+1]))
            {
                int t=A[j];
                A[j]=A[j+1];
                A[j+1]=t;
            }
        }
    }
    for(int i=0;i<SIZE;i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
Input:
87 181 9 5
Output:
9 87 5 181

Reverse the adjacent nodes in a linked list

Reverse the adjacent nodes of a linked list as described below in the sample input and output:
Input 1: 1->2->3->4->5
Output1: 2->1->4->3->5
Input2: 1->2->3->4->5->6
Output2: 2->1->4->3->6->5

#include<iostream>
#include<stdlib.h>
using namespace std;

struct node
{
    int data;
    struct node* next;
};

struct node* createlist(int length)
{
    struct node *root=NULL,*end=NULL;
    for(int i=1;i<=length;i++)
    {
        struct node* new_node = (struct node*)malloc(sizeof(struct node));
        new_node->data=i;
        new_node->next=NULL;
        if(i==1)
        {
            root=new_node;
            end=root;
        }
        else
        {
            end->next=new_node;
            end=new_node;
        }
    }
    return root;
}
struct node* reverseadjacent(struct node* root)
{
    int length=0;
    struct node *temp=root;
    while(temp!=NULL)
    {
        length++;
        temp=temp->next;
    }
    if(length<2)
    {
        return root;
    }
    struct node *first=root,*sec=first->next,*third=sec->next;
    root=first->next;
    if(length==2)
    {
        sec->next=first;
        first->next=NULL;
    }
    else if(length%2==0)
    {
        while(third!=NULL)
        {
            first->next=third->next;
            sec->next=first;
            first=third;
            sec=third->next;
            third=sec->next;
        }
        sec->next=first;
        first->next=NULL;
    }
    else
    {
        while(third->next!=NULL)
        {
            first->next=third->next;
            sec->next=first;
            first=third;
            sec=third->next;
            third=sec->next;
        }
        sec->next=first;
        first->next=third;
    }
    return root;
}
void printlist(struct node* root)
{
    struct node* temp=root;
    while(temp!=NULL)
    {
        cout<<temp->data<<"->";
        temp=temp->next;
    }
    cout<<endl;
}
int main()
{
    struct node* root=createlist(5);
    cout<<"The given list\n";
    printlist(root);
    struct node* new_root=reverseadjacent(root);
    cout<<"The new list\n";
    printlist(new_root);
}

Printing all nodes at a given distance from a starting node in a binary tree

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    return new_node;
};
int printKDistance(node* root,node* start,int k,int *found)
{
    if(root)
    {
        //cout<<root->data<<endl;
        if(k==0)
        {
            cout<<root->data<<endl;
        }
        else if(root==start || *found==1)
        {
            *found=1;
            printKDistance(root->left,start,k-1,found);
            printKDistance(root->right,start,k-1,found);
            return 1;
        }
        else if(*found==0)
        {
            int ldist = printKDistance(root->left,start,k,found);
            //cout<<"ldist="<<ldist<<endl;
            int rdist=0;
            if(*found==0)
            {
                rdist = printKDistance(root->right,start,k,found);
            }
            if((ldist == k || rdist == k) && *found==1)
            {
                cout<<root->data<<endl;
            }
            else
            {
                if(ldist!=0 || rdist!=0)
                return ldist>rdist?1+ldist:1+rdist;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    int k=2;
    //struct node* start = root->right->right->left;
    struct node* start = root->right->left;
    cout<<"start node="<<start->data<<endl;
    cout<<"k="<<k<<endl;
    int a=0;
    int *found=&a;
    printKDistance(root,start,k,found);
}
Output:
start node=7
k=2
Node: 1

Integer Expression Evaluator using Infix-to-Postfix conversion and evaluation of Postfix expression

#include<iostream>
#include<string.h>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

class stack
{
    private:
        int top;
        char A[100];//operator stack array
        int B[100];//operand stack array
    public:
        char pop_oprt();
        void undopop_oprt();
        void push_oprt(char);
        int get_top();
        void displayoprt();
        void init();
        void push_opnd(int);
        int pop_opnd();
};
void stack::init()
{
    top=-1;
}
char stack::pop_oprt()
{
    if(top==-1)
    {
        return 0;
    }
    else
    {
        char t = A[top];
        top--;
        return t;
    }
}
void stack::push_oprt(char val)
{
    top++;
    A[top]=val;
}
void stack::undopop_oprt()
{
    top++;
}
int stack::pop_opnd()
{
    int t = B[top];
    top--;
    return t;
}
void stack::push_opnd(int val)
{
    top++;
    B[top]=val;
}
int stack::get_top()
{
    return top;
}
void stack::displayoprt()
{
    for(int i=top;i>=0;i--)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
int prcd(char a)
{
    if(a=='(')
    {
        return 0;
    }
    else if(a=='+')
    {
        return 1;
    }
    else if(a=='-')
    {
        return 1;
    }
    else if(a=='/')
    {
        return 2;
    }
    else if(a=='*')
    {
        return 2;
    }
}
int evaluator(char post[100][10],int cnt)
{
    stack opnd;
    opnd.init();
    int i=0;
    while(i<cnt)
    {
        if(isdigit(post[i][0]))
        {
            opnd.push_opnd(atoi(post[i]));
            //opnd.displayoprt();
        }
        else
        {
            int val2 = opnd.pop_opnd();
            int val1 = opnd.pop_opnd();
            if(post[i][0]=='*')
            {
                opnd.push_opnd(val1*val2);
            }
            else if(post[i][0]=='+')
            {
                opnd.push_opnd(val1+val2);
            }
            else if(post[i][0]=='-')
            {
                opnd.push_opnd(val1-val2);
            }
            else if(post[i][0]=='/')
            {
                opnd.push_opnd(val1/val2);
            }
        }
        i++;
    }
    return opnd.pop_opnd();
}
int main()
{
    //char A[100] = "4/2*2+2/2*4";
    char A[100] = "(11+2)*(3+4)";
    stack oprt;
    oprt.init();
    char post[100][10];
    int cnt=00;
    for(int i=0;i<strlen(A);)
    {
        //oprt.displayoprt();
        //getchar();
        int curr_num=0;
        if(isdigit(A[i]))
        {
            while(isdigit(A[i]))
            {
                curr_num = curr_num*10 + A[i]-48;
                i++;
            }
            itoa(curr_num,post[cnt],10);
            cnt++;
        }
        else if(A[i]=='(')
        {
            oprt.push_oprt(A[i]);
            i++;
        }
        else if(A[i]==')')
        {
            while(oprt.pop_oprt()!='(' && oprt.get_top()>-1)
            {
                oprt.undopop_oprt();
                post[cnt][0]=oprt.pop_oprt();
                post[cnt][1]=0;
                cnt++;
            }
            i++;
        }
        else
        {
            //oprt.diplayoprt();
            if(oprt.get_top()==-1)
            {
                oprt.push_oprt(A[i]);
                //cout<<oprt.pop_oprt()<<endl;
            }
            else if(prcd(A[i])>prcd(oprt.pop_oprt()))
            {
                oprt.undopop_oprt();
                oprt.push_oprt(A[i]);
            }
            else
            {
                oprt.undopop_oprt();
                post[cnt][0]=oprt.pop_oprt();
                post[cnt][1]=0;
                cnt++;
                oprt.push_oprt(A[i]);
            }
            i++;
        }
    }
    while(oprt.get_top()>=0)
    {
        post[cnt][0]=oprt.pop_oprt();
        post[cnt][1]=0;
        cnt++;
    }
    cout<<"post-fix"<<endl;
    for(int i=0;i<cnt;i++)
    {
        cout<<post[i]<<endl;
    }
    cout<<"Final value"<<endl;
    cout<<evaluator(post,cnt)<<endl;
}
Output: 91

Finding the Lowest Common Ancestor of two given nodes in a Binary Tree

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* next;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    new_node->next=NULL;
    return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
    if(root)
    {
        if(root==n1)
        {
            return 1;
        }
        else if(root==n2)
        {
            return 1;
        }
        else
        {
            return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
        }
    }
    else
    {
        return 0;
    }
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
    if(root)
    {
        int lf = help_anc(root->left,n1,n2);
        int rf = help_anc(root->right,n1,n2);
        if(lf==1 && rf==1)
        {
            return root;
        }
        else
        {
            node* lca = Ancestor(root->left,n1,n2);
            if(lca!=NULL)
            {
                return lca;
            }
            lca = Ancestor(root->right,n1,n2);
            return lca;
        }
    }
    else
    {
        return NULL;
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    struct node* n1 = root->right->right->right;
    struct node* n2 = root->left->left;
    struct node* lca=Ancestor(root,n1,n2);
    if(lca)
    {
 cout<<lca->data<<endl;
    }
}
Output:
1

Inorder, Preorder and Postorder Successor and Predecessor Functions inC++

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* next;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    new_node->next=NULL;
    return new_node;
}
void inord_succ(struct node* root,struct node** prev)
{
    if(root)
    {
        inord_succ(root->left,prev);
        if(*prev!=NULL)
        {
            (*prev)->next = root;
            *prev = root;
        }
        else
        {
            *prev = root;
        }
        inord_succ(root->right,prev);
    }
}
void inord_pred(struct node* root,struct node** prev)
{
    if(root)
    {
        inord_pred(root->left,prev);
        root->next=*prev;
        *prev=root;
        inord_pred(root->right,prev);
    }
}
void preord_succ(struct node* root,struct node** prev)
{
    if(root)
    {
        if(*prev!=NULL)
        {
            (*prev)->next=root;
            *prev=root;
        }
        else
        {
            *prev=root;
        }
        preord_succ(root->left,prev);
        preord_succ(root->right,prev);
    }
}
void preord_pred(struct node* root,struct node** prev)
{
    if(root)
    {
        root->next=*prev;
        *prev=root;
        preord_pred(root->left,prev);
        preord_pred(root->right,prev);
    }
}
void postord_succ(struct node* root,struct node** prev)
{
    if(root)
    {
        postord_succ(root->left,prev);
        postord_succ(root->right,prev);
        if(*prev!=NULL)
        {
            (*prev)->next=root;
            *prev=root;
        }
        else
        {
            *prev=root;
        }
    }
}
void postord_pred(struct node* root,struct node** prev)
{
    if(root)
    {
        postord_pred(root->left,prev);
        postord_pred(root->right,prev);
        root->next=*prev;
        *prev=root;
    }
}
void inorder(struct node* root)
{
    if(root)
    {
 inorder(root->left);
 cout<<root->data<<" ";
 if(root->next)
 {
     cout<<root->next->data<<endl;
 }
 else
 {
     cout<<endl;
 }
 inorder(root->right);
    }
}
void preorder(struct node* root)
{
    if(root)
    {
        cout<<root->data<<" ";
        if(root->next)
        {
            cout<<root->next->data<<endl;
        }
        else
        {
            cout<<endl;
        }
        preorder(root->left);
        preorder(root->right);
    }
}
void postorder(struct node* root)
{
    if(root)
    {
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<" ";
        if(root->next)
        {
            cout<<root->next->data<<endl;
        }
        else
        {
            cout<<endl;
        }
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    struct node* ptr = NULL;
    //inord_succ(root,&ptr);
    //inord_pred(root,&ptr);
    //inorder(root);
    //preord_succ(root,&ptr);
    //preord_pred(root,&ptr);
    //preorder(root);
    //postord_succ(root,&ptr);
    postord_pred(root,&ptr);
    postorder(root);
    cout<<endl;
}

Number of closed rectangles in a matrix

Given a matrix containing only 1 and 0, find the number of closed rectangles. A closed rectangle is represented by at least one 0 surrounded by eight 1's. There is no overlap of closed rectangles.

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt);
    int A[][10]={
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,1,1,1,1,1,0,0,0},
        {0,0,1,0,0,0,1,0,0,0},
        {0,0,1,0,0,0,1,0,0,0},
        {0,0,1,1,1,1,1,0,0,0},
        {1,1,1,0,0,0,1,1,1,1},
        {0,0,1,0,0,0,1,0,1,1},
        {1,1,1,0,0,0,1,1,1,1}
    };
    int cnt=0;
	for(int i=0;i<8;i++)
    {
        for(int j=0;j<10;j++)
        {
            cout<<A[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(A[i][j]>0)
            {
                cnt=rectangle(A,i,j,8,10,cnt);
            }
        }
    }
    cout<<"The number of closed rectangles is: "<<cnt<<endl;
}

int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt)
{
    cnt++;
    int rnd=1;
    if(i<d1-1 && j<d2-1 && A[i+1][j+1]==0)
    {
		j++;
		while(j<d2 && i<d1-1 && A[i][j]==1 && A[i+1][j]==0)
		{
			A[i][j]=-1*cnt;
			j++;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(i<d1-1 && j>0 && A[i+1][j-1]==0 && A[i][j]==-1*cnt)
	{
		i++;
		while(i<d1 && j>0 && A[i][j]==1 && A[i][j-1]==0)
		{
			A[i][j]=-1*cnt;
			i++;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(i>0 && j>0 && A[i-1][j-1]==0 && A[i][j]==-1*cnt)
	{
		j--;
		while(j>=0 && i>0 && A[i-1][j]==0 && A[i][j]==1)
		{
			A[i][j]=-1*cnt;
			j--;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(i>0 && j<d2-1 && A[i-1][j+1]==0 && A[i][j]==-1*cnt)
	{
		i--;
		while(i>=0 && j<d2-1 && A[i][j+1]==0 && A[i][j]==1)
		{
			A[i][j]=-1*cnt;
			i--;
		}
		A[i][j]=-1*cnt;
		rnd++;
	}
	if(rnd!=5 || (A[i][j]!=0 && A[i][j]!=A[i][j+1]))
	{
		cnt--;
	}
        return cnt;
}
Output:
The number of closed rectangles is: 2

Android Translation Apps

Useful links are as follow:
1. Using Bing translation API:
http://www.microsoft.com/web/post/using-the-free-bing-translation-apis
2. Using Google Translation API:
http://rupeshpatel.wordpress.com/2012/06/23/usage-of-google-translator-api-for-free/
3. Link for Google Translator App:
https://play.google.com/store/apps/details?id=com.google.android.apps.translate&hl=en
4. Link for iTranslate App:
https://play.google.com/store/apps/details?id=at.nk.tools.iTranslate&hl=en
5. A nice Translator App with video demo:
http://www.cellictica.com/products.html#
6. List of Translator Apps:
http://android.appstorm.net/roundups/utilities-roundups/translation-apps-roundup/

Using Text to Speech API in Android

Useful links are as follow:
1. App developed using the tts engine:
http://mobile.tutsplus.com/tutorials/android/android-sdk-using-the-text-to-speech-engine/
2. Android link to use the tts API:
http://developer.android.com/reference/android/speech/tts/TextToSpeech.html
3. Android Sample Text-to-Speech API usage:
http://android-developers.blogspot.in/2009/09/introduction-to-text-to-speech-in.html
4. Voice Recorder App in Android:
https://play.google.com/store/apps/details?id=com.tokasiki.android.voicerecorder&hl=en

Using Speech to Text API in Android

Useful links are as follow:
1. Good google search string: speech to text api android
2. Android emulator is not capable of audio record:
http://www.deveature.com/2011/11/28/speech-recognizer-does-not-work-on-android-emulator/
3. Audio-capture in android:
http://developer.android.com/guide/topics/media/audio-capture.html
4. Stack overflow link for using MediaRecorder in Android:
http://stackoverflow.com/questions/5254994/can-the-android-emulator-record-and-play-back-audio-using-pc-hardware
5. App developed using Recognizer Intent (speech-to-text API):
http://viralpatel.net/blogs/android-speech-to-text-api/
6. Speech Input API for Android:
http://android-developers.blogspot.in/2010/03/speech-input-api-for-android.html
7. Link for Android Sample Projects:
http://developer.android.com/tools/samples/index.html
8. Recognizer Intent in Android:
http://developer.android.com/reference/android/speech/RecognizerIntent.html
9. SDK Version Concept in Android:
http://developer.android.com/guide/topics/manifest/uses-sdk-element.html
10. Voice Search app in Android:
https://play.google.com/store/apps/details?id=com.google.android.voicesearch&feature=search_result

Two Ends

In the two-player game “Two Ends”, an even number of cards is laid out in a row. On each card, face up, is written a positive integer. Players take turns removing a card from either end of the row and placing the card in their pile. The player whose cards add up to the highest number wins the game. Now one strategy is to simply pick the card at the end that is the largest — we’ll call this the greedy strategy. However, this is not always optimal, as the following example shows: (The first player would win if she would first pick the 3 instead of the 4.)

3 2 10 4

You are to determine exactly how bad the greedy strategy is for different games when the second player uses it but the first player is free to use any strategy she wishes.

Input

There will be multiple test cases. Each test case will be contained on one line. Each line will start with an even integer n followed by n positive integers. A value of n = 0 indicates end of input. You may assume that n is no more than 1000. Furthermore, you may assume that the sum of the numbers in the list does not exceed 1,000,000.

Output

For each test case you should print one line of output of the form:

In game m, the greedy strategy might lose by as many as p points.

where m is the number of the game (starting at game 1) and p is the maximum possible difference between the first player’s score and second player’s score when the second player uses the greedy strategy. When employing the greedy strategy, always take the larger end. If there is a tie, remove the left end.

Example

Input:
4 3 2 10 4
8 1 2 3 4 5 6 7 8
8 2 2 1 5 3 8 7 3
0

Output:
In game 1, the greedy strategy might lose by as many as 7 points.
In game 2, the greedy strategy might lose by as many as 4 points.
In game 3, the greedy strategy might lose by as many as 5 points.

#include<iostream>
using namespace std;
int max=0;
int main()
{
 int A[100],n,game=1;
 int fun(int A[],int low,int high,int s1,int s2,int turn);
 while(cin>>n)
 {
  if(n==0)
  {
   break;
  }
  else
  {  
   for(int i=0;i<n;i++)
   {
    cin>>A[i];
   }
   int turn=1,low=0,high=n-1,s1=0,s2=0;
   ::max=0;
   ::max=fun(A,low,high,s1,s2,turn);
  }
  cout<<"In game "<<game<<", the greedy strategy might lose by as many as "<<::max<<" points."<<endl;
  game++;
 }
 return 0;
}
int fun(int A[],int low,int high,int s1,int s2,int turn)
{
 //static int max=0;
 if(low>high)
 {
  if(::max<s1-s2)
  {
   ::max=s1-s2;
  }
  return ::max;
 }
 else if(turn==1)
 {
  s1+=A[low];
  turn=2;
  fun(A,low+1,high,s1,s2,turn);
  s1-=A[low];
  s1+=A[high];
  fun(A,low,high-1,s1,s2,turn);
 }
 else if(turn==2)
 {
  turn=1;
  if(A[low]>=A[high])
  {
   s2+=A[low];
   fun(A,low+1,high,s1,s2,turn);
  }
  else
  {
   s2+=A[high];
   fun(A,low,high-1,s1,s2,turn);
  }
 }
}

Counting discrete clusters of 1 in a binary 2D matrix

#include<iostream>
using namespace std;
int main()
{
	int A[100][100];
	int m,n;
	void fun(int A[][100],int i,int j,int c,int m,int n);
	cin>>m>>n;
	int c=0;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>A[i][j];
		}
	}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(A[i][j]>0)
			{
				c++;
				fun(A,i,j,c,m,n);
			}
		}
	}
	cout<<c<<endl;
	return 0;
}
void fun(int A[][100],int i,int j,int c,int m,int n)
{
	A[i][j]=-1*c;
	if(i>0 && j>0 && A[i-1][j-1]>0)
	{
		fun(A,i-1,j-1,c,m,n);
	}
	if(i>0 && j>=0 && j<n && A[i-1][j]>0)
	{
		fun(A,i-1,j,c,m,n);
	}
	if(i>0 && j<n-1 && A[i-1][j+1]>0)
	{
		fun(A,i-1,j+1,c,m,n);
	}
	if(i>=0 && i<n && j<n-1 && A[i][j+1]>0)
	{
		fun(A,i,j+1,c,m,n);
	}
	if(i<n-1 && j<n-1 && A[i+1][j+1]>0)
	{
		fun(A,i+1,j+1,c,m,n);
	}
	if(i<n-1 && j<n && j>=0 && A[i+1][j]>0)
	{
		fun(A,i+1,j,c,m,n);
	}
	if(i<n-1 && j>0 && A[i+1][j-1]>0)
	{
		fun(A,i+1,j-1,c,m,n);
	}
	if(i<n && i>=0 && j>0 && A[i][j-1]>0)
	{
		fun(A,i,j-1,c,m,n);
	}
}
Sample Input:
3 5
1 1 1 0 0
0 0 1 0 1
0 1 0 1 1

Output:
1

Counting the number of valid bracket permutations for a given length

Example:
Input: 3
Output: 5
Explanation: The following permutations are valid:
((())),(())(),()(()),(()()),()()()
The following permutations are invalid:
)()()(,())(() etc.
Program:
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int main()
{
 int fun(char[],int,int,int);
 int n;
 cin>>n;
 char A[100]="";
 cout<<fun(A,0,0,n)<<endl;
}
int fun(char A[],int open,int close,int n)
{
 static int count=0;
 if(open-close<0 || open-close>n || open>n)
 {
  return count;
 }
 else if(strlen(A)==2*n)
 {
  //cout<<A<<endl;
  count++;
  //cout<<count<<" "<<endl;
  return count;
 }
 else
 {
  A[strlen(A)]='(';
  A[strlen(A)+1]=0;
  fun(A,open+1,close,n);
  A[strlen(A)-1]=0;
  A[strlen(A)]=')';
  A[strlen(A)+1]=0;
  fun(A,open,close+1,n);
  A[strlen(A)-1]=0;
  return count;
 }
}
Sample Input: 15
Sample Output: 9694845

Directory Path Parsing

Input: "C:\\a\\b\\c\\..\\.\\..\\g\\."
Output: "C:\\a\\g"

#include<iostream>
#include<string.h>
#include<signal.h>
using namespace std;
int main()
{
 void fun();
 char A[100]="C:\\a\\b\\c\\..\\.\\..\\g\\.\\..";
 //char A[100]="C:\\a\\b";
 char B[100]="";
 char temp[100]="";
 int top=-1;
 char C[20][100];
 int i=0;
 while(i<strlen(A) && A[i]!='\\')
 {
  B[i]=A[i];
  i++;
 }
 B[i]=0;
 while(i<strlen(A))
 {
  int j=0;
  while(i<strlen(A) && A[i]!='\\')
  {
   temp[j]=A[i];
   i++;
   j++;
  }
  temp[j]=0;
  if(top>=0 && strcmp(temp,"..")==0)
  {
   top--;
  }
  else if(strcmp(temp,".")==0)
  {
  }
  else
  {
   top++;
   strcpy(C[top],temp);
  }
  i++;
 }
 for(int j=0;j<=top;j++)
 {
  strcat(B,C[j]);
  strcat(B,"\\");
 }
 cout<<B<<endl;
}

Grid Traversal

There is a rectangular grid of size m * n . Bob is in location ( x, y ) inside grid. He can move in 4 directions up, down, right and left. He will die if he steps outside of rectangular grid. Find the probability that bob is alive given initial position of bob as ( x, y ) and number of steps he moves as N. (Given that Bob moves only one step at a time).

#include<iostream>
using namespace std;
int main()
{
    void fun(int,int,int,int,float*,float*,int,int);
    int m,n,x,y,N;
    float a=0.0,b=0.0,*p=&a,*q=&b;
    cin>>m>>n>>x>>y>>N;
    fun(m,n,x,y,p,q,0,N);
    cout<<(*q)/((*q)+(*p));
}
void fun(int m,int n,int x,int y,float *p,float *q,int S,int N)
{    
    if(S==N && x>=0 && y>=0 && x<m && y<n)
    {
        (*q)++;
        return;
    }
    else if((S<=N) && (x<0 || y<0 || x>=m || y>=n))
    {
        (*p)++;
        return;
    }
    else
    {
        fun(m,n,x+1,y,p,q,S+1,N);
        fun(m,n,x-1,y,p,q,S+1,N);
        fun(m,n,x,y+1,p,q,S+1,N);
        fun(m,n,x,y-1,p,q,S+1,N);
    }
}

Excel column header generator

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
        char out[27]={'Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y',0};
        char ans[100]={0};
        int t;
        cin>>t;
        while(t--)
        {
                int n;
                cin>>n;
                int j=0;
                while(n>0)
                {
                        int c=n%strlen(out);
                        //Using the remainder as the index of the character array.
                        ans[j]=out[c];
                        if(c==0)
                        {
                                n--;
                        }
                        n/=strlen(out);
                        j++;
                }
                //Reversing the answer string.
                for(int i=0;i<strlen(ans)/2;i++)
                {
                        char t=ans[i];
                        ans[i]=ans[strlen(ans)-i-1];
                        ans[strlen(ans)-i-1]=t;
                }
                cout<<ans<<endl;
        }
        return 0;
}

Sample Input: The first line is the number of test cases.
7
1
25
26
27
51
52
676

Sample Output:
A
Y
Z
AA
AY
AZ
YZ

C++ Program for Quicksort

#include<iostream>
using namespace std;
int main()
{
        int A[7]={3,6,1,2,7,5,4};
        void quicksort(int[],int,int);
        quicksort(A,0,6);
        for(int i=0;i<7;i++)
        {
                cout<<A[i]<<" ";
        }
        cout<<endl;         
        return 0; 
} 
void quicksort(int A[7],int low,int high) 
{         
        if(low>=high)
        {
                return;
        }
        int p=A[low];
        int i=low+1;
        int j=high;
        while(j>=i)
        {
                while(A[i]<=p)
                {
                         i++;                 
                }
                while(A[j]>p)
                {
                        j--;
                }
                if(j>i)
                {
                        int t=A[i];
                        A[i]=A[j];
                        A[j]=t;
                }
        }
        int t=A[j];
        A[j]=A[low];
        A[low]=t;
        quicksort(A,low,j-1);
        quicksort(A,j+1,high);
}

C++ Program for Mergesort

#include<iostream>
using namespace std;
int main()
{
        void mergesort(int[],int,int);
        int A[7]={1,2,5,3,7,6,4};
        int low=0,high=6;
        mergesort(A,0,6);
        for(int i=low;i<=high;i++)
        {
                cout<<A[i]<<" ";
        }
        cout<<endl;
        return 0;
}
void mergesort(int A[7],int low,int high)
{
        if(low==high)
        {
                return;
        }
        int mid=(low+high)/2;
        mergesort(A,low,mid);
        mergesort(A,mid+1,high);
        int a=low;
        int b=mid+1;
        int B[100],j=0;
        while(a<=mid && b<=high)
        {
                if(A[a]<A[b])
                {
                        B[j]=A[a];
                        j++;
                        a++;
                }
                else if(A[b]<A[a])
                {
                        B[j]=A[b];
                        j++;
                        b++;
                }
        }
        while(a<=mid)
        {
                B[j]=A[a];
                j++;
                a++;
        }
        while(b<=high)
        {
                B[j]=A[b];
                j++;
                b++;
        }
        int k=0;
        for(int i=low;i<=high;i++)
        {
                A[i]=B[k];
                k++;
        }
}

Given an array of positive integers, print out all the numbers which are repeated an even number of times without using additional storage

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text.RegularExpressions;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            //This part assumes that all the elements in the array lie in the range (min,min + arraylength -1).
            int[] arr1 = { 1, 2, 3, 4, 4, 5, 2, 1, 1, 1 };
            int count = 1;
            int min = arr1.Min();
            int max = arr1.Max();
            for (int i = 0; i < arr1.GetLength(0); i++)
            {
                arr1[Math.Abs(arr1[i])] *= -1;
            }
            for (int i = 0; i < arr1.GetLength(0); i++)
            {
                Console.Write(arr1[i] + " ");
            }
            Console.WriteLine();
            for (int i = min; i <= max; i++)             {                 if (arr1[i] > 0)
                {
                    Console.Write(i + " ");
                }
            }
            Console.WriteLine();
            //This part sorts the array and finds the frequency map and counts the frequency of each element.
            int[] arr2 = { 1, 2, 3, 4, 4, 5, 2, 1, 1, 1 };
            Array.Sort(arr2);
            for (int i = 0; i < arr2.GetLength(0) - 1; i++)
            {
                count = 1;
                while (arr2[i + 1] == arr2[i])
                {
                    i++;
                    count++;
                }
                if (count % 2 == 0)
                {
                    Console.WriteLine(arr2[i] + " " + count);
                }
            }
        }
    }
}

Printing the max length substring with max repetition count

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text.RegularExpressions;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            int[] maxcount = new int[str.Length + 1];
            string[] maxstring = new string[str.Length + 1];
            for (int i = 0; i < str.Length; i++)//Starting point of the substring to be searched.
            {
                for (int length = 1; length <= str.Length - i; length++)//Length of the substring to be searched.
                {
                    int count = 0;
                    string substr1 = str.Substring(i, length);
                    for (int j = 0; j <= str.Length - length; j++)//Starting point in the string from where the search starts.
                    {
                        string substr2 = str.Substring(j, length);
                        if (substr1 == substr2)
                        {
                            count++;
                        }
                    }
                    if (maxcount[length] < count)
                    {
                        maxcount[length] = count;
                        maxstring[length] = substr1;
                    }
                }
            }
            int maxcnt = 0;
            string maxstr="";
            for (int i = 1; i <= str.Length; i++)
            {
                if (maxcnt <= maxcount[i])
                {
                    maxcnt = maxcount[i];
                    maxstr = maxstring[i];
                }
            }
            Console.WriteLine(maxstr + " has the max length: " + maxcnt);
        }
    }
}
abcabcabcabc
abc has the max length: 4
Press any key to continue . . .

C Program to write the permutations of the characters of a string using Recursion

#include<stdio.h>
#include<string.h>
int main()
{
 void permute(char[],char[],int[],int,int);
 char A[100];
 scanf("%s",A);
 char B[100]="";
 int length=strlen(A);
 int level=0;
 int used[100]={0};
 permute(A,B,used,length,level);
 return 0;
}
void permute(char* A,char* B,int* used,int length,int level)
{
 if(level==length)
 {
  B[level]='';
  printf("%s\n",B);
  return;
 }
 else
 {
  for(int i=0;i<length;i++)
  {
   if(used[i]==1)
   {
    continue;
   }
   used[i]=1;
   B[level]=A[i];
   permute(A,B,used,length,level+1);
   used[i]=0;
   B[level]='';
  }
  return;
 }
}

Alternating Letters

An alternation in a string is defined to be two distinct characters (letters, digits, or punctuation) that alternate at least three times as the word is read from left to right. The word “boo” has no alternations, but “booboo” has “bobo” as an alternation of length 4. Upper and lower case characters are considered to be different, and so, “aragorn” contains the 4-element alternation “arar”, but “Aragorn” only has the 3-element alternation “rar”. Digits and punctuation may be used, so “a2b-c2d-” has the alternation “2-2-”. The objective of this problem is to write a program to find the length of the longest alternation in a word.
Examples:

Input	Output	Explanation
exasperated	Length = 5	eaeae
counterintuitive	Length = 6	tititi
insignificant	Length = 6	ininin
Aragorn	Length = 3	rar
a2b-c2d-	Length = 4	2-2-
cat	Length = 0	No subsequence having length > 3
ca	Length = 0	No subsequence having length > 3

#include<stdio.h>
#include<string.h>
int main()
{
        int A[256]={0},max=0,B[256]={0};
        char s[1000];
        scanf("%s",s);
        for(int i=0;i<strlen(s);i++)
        {
                A[s[i]]++;
                if(s[i]>max)
                {
                        max=s[i];
                }
        }
        int k=0;
        for(int i=0;i<=max;i++)
        {
                if(A[i]!=0)
                {
                        B[k]=i;
                        k++;
                }
        }
        int maxcount=0;
        for(int i=0;i<k;i++)
        {
                for(int j=i+1;j<k;j++)
                {
                        int count=0;
                        int order=0;
                        char curr='';
                        for(int c=0;c<strlen(s);c++)
                        {
                                if(s[c]==B[i])
                                {
                                        if(order==0)
                                        {
                                                count++;
                                                order=1;
                                                curr=B[i];
                                        }
                                        else if(curr==B[j])
                                        {
                                                count++;
                                                curr=B[i];
                                        }
                                }
                                else if(s[c]==B[j])
                                {
                                        if(order==0)
                                        {
                                                count++;
                                                order=1;
                                                curr=B[j];
                                        }
                                        else if(curr==B[i])
                                        {
                                                count++;
                                                curr=B[j];
                                        }
                                }
                        }
                        if(maxcount<count)
                        {
                                maxcount=count;
                        }
                }
        }
        if(maxcount>=3)
        {
                printf("%d\n",maxcount);
        }
        else
        {
                printf("0\n");
        }
        return 0;
}

Simple Minded Hashing

All of you know a bit or two about hashing. It involves mapping an element into a numerical value using some mathematical function. In this problem we will consider a very ‘simple minded hashing’. It involves assigning numerical value to the alphabets and summing these values of the characters.

For example, the string “acm” is mapped to 1 + 3 + 13 = 17. Unfortunately, this method does not give one-to-one mapping. The string “adl” also maps to 17 (1 + 4 + 12). This is called collision.

In this problem you will have to find the number of strings of length L, which maps to an integer S, using the above hash function. You have to consider strings that have only lowercase letters in strictly ascending order.

Suppose L = 3 and S = 10, there are 4 such strings.

1. abg


2. acf


3. ade


4. bce

agb also produces 10 but the letters are not strictly in ascending order.

bh also produces 10 but it has 2 letters.

Input

There will be several cases. Each case consists of 2 integers L and S. (0 < L, S < 10000). Input is terminated with 2 zeros.

Output

For each case, output Case #: where # is replaced by case number. Then output the result. Follow the sample for exact format. The result will fit in 32 bit signed integers.

Sample Input	Output for Sample Input
3 10 2 3 0 0	Case 1: 4 Case 2: 1

#include<stdio.h>
int main()
{
 int fun(int,int,int,int,int,int,int[]);
 int t,inp,num,A[10000]={0};
 scanf("%d %d",&inp,&num);
 if(inp==0 && num==0)
 {
  return 0;
 }
 else
 {
  printf("Count= %d\n",fun(1,inp,0,0,num,0,A));
 }
 return 0;
}
int fun(int level,int inp,int sum,int curr,int num,int count,int A[10000])
{
 if(level==inp)
 {
  if(num-sum<=26 && num-sum>curr)
  {
   for(int i=0;i<level-1;i++)
   {
    printf("%d ",A[i]);
   }
   printf("%d\n",num-sum);
   count+=1;
   return count;
  }
  else
  {
   return count;
  }
 }
 else
 {
  for(int i=curr+1;i<=(num/(inp-1));i++)
  {
   sum+=i;
   A[level-1]=i;
   count=fun(level+1,inp,sum,i,num,count,A);
   sum-=i;
  }
  return count;
 }
}

Determinant Calculator

C-program to calculate the determinant of a square matrix of any dimensions up to [100x100]

#include<stdio.h>
int main()
{
 int determinant(int A[][100],int n,int i,int s);
 int A[100][100],i,n,B[100];
 printf("Enter the number of rows or columns: \n");
 scanf("%d",&n);
 printf("Enter the square matrix: \n");
 for(int i=0;i<n;i++)
 {
  for(int j=0;j<n;j++)
  {
   scanf("%d",&A[i][j]);
  }
 }
 printf("The determinant is: \n");
 int s=0;
 s=determinant(A,n,i,s);
 printf("%d\n",s);
 fflush(stdin);
 getchar();
 return 0;
}
int determinant(int A[][100],int n,int i,int s)
{
 int B[100][100];
 int a=s;
 if(n==2)
 {
  return A[0][0]*A[1][1] - A[0][1]*A[1][0];
 }
 else
 {
  //int s=0;
  for(int j=0;j<n;j++)
  {
   int x=0;
   for(int p=1;p<n;p++)
   {
    int y=0;
    for(int q=0;q<n;q++)
    {
     if(q!=j)
     {
      B[x][y]=A[p][q];
      y++;
     }
    }
    x++;
   }
   if(j%2==0)
   {
    s+=A[0][j]*determinant(B,n-1,j,a);
   }
   else
   {
    s-=A[0][j]*determinant(B,n-1,j,a);
   }
  }
  return s;
 }
}
Output:
Enter the number of rows or columns: 4
Enter the square matrix: 
1 13 4 6
23 21 18 5
4 2 7 9
1 10 15 12
The determinant is: 
20353

Merging non-overlapping intervals

Problem:

Given a set of non overlapping intervals
Example 1: (1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)

Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)
New interval (14, 33)
Output should be
(1,5) (6, 33) (35, 40)

This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)

Input:

The first line contains a number T, the number of test cases.

The next line contains an integer N, which is the number of non-overlapping intervals.

The next N lines contain two space separated integers which denote the start and end points of an interval. This is followed by a blank line.

The next line contains two space separated integers which denote the new interval.

Output:

The output for each test case should contain a line of the form “Case #X: “ where X is the number of the test case.

The next lines should contain the merged intervals in the ascending order.

C++ Code:

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
 int A[100],B[100],t,a,b,n,d=1;
 cin>>t;
 while(t--)
 {
  int m=1;
  cin>>n;
  for(int i=0;i<n;i++)
  {
   cin>>A[i];
   cin>>B[i];
  }
  sort(A,A+n);
  sort(B,B+n);
  cin>>a>>b;
  int j=0;
  while(j<=n-1 && a>A[j] && a>B[j])
  {
   j++;
  }
  int k=n-1;
  while(k>=0 && b<B[k] && b<A[k])
  {
   k--;
  }
  if(j<k)
  {
   if(a<A[j])
   {
    A[j]=a;
   }
   if(b>B[k])
   {
    B[j]=b;
   }
   else
   {
    B[j]=B[k];
   }
  }
  else if(j>k)
  {
   m=0;
  }
  else
  {
   if(B[j]<b)
   {
    B[j]=b;
   }
  }
  if(m==1)
  {
   cout<<"Case #"<<d<<": "<<endl;
   for(int i=0;i<=j;i++)
   {
    cout<<A[i]<<" "<<B[i]<<endl;
   }
   for(int i=k+1;i<n;i++)
   {
    cout<<A[i]<<" "<<B[i]<<endl;
   }
  }
  else
  {
   cout<<"Case #"<<d<<": "<<endl;
   for(int i=0;i<j;i++)
   {
    cout<<A[i]<<" "<<B[i]<<endl;
   }
   cout<<a<<" "<<b<<endl;
   for(int i=k+1;i<n;i++)
   {
    cout<<A[i]<<" "<<B[i]<<endl;
   }
  }
  d++;
 }
 return 0;
}
Sample Input:
1
6
1 5
6 15
20 21
23 26
27 30
35 40
14 33
Sample Output:
Case #1:
1 5
6 33
35 40

Find the next higher number with the same digits

//Code to find the next higher number with the same digits.
#include<iostream>
using namespace std;
int main()
{
 long long int m,n,A[1000],i,j,k,temp,same;
 cin>>n;
 same=0;
 i=0;
 while(n>0)
 {
  A[i]=n%10;
  n=n/10;
  i++; 
 } 
 //Finding the first digit at which the next digit is less than this digit starting from the left.
 for(j=0;j<i-1;j++)
 {
  if(A[j+1]<A[j])
  {
   //Finding the smallest digit greater than the pivotal digit.
   for(k=0;k<=j;k++)
   {
    if(A[k]>A[j+1])
    {
     break; 
    }
   }
   //Swapping the two digits.
   temp=A[k];
   A[k]=A[j+1]; 
   A[j+1]=temp; 
   same=1;
   break; 
  } 
 }
 //If the next higher number is possible with the same number of digits
 if(same==1)
 {
  m=A[i-1];
  for(k=i-2;k>j;k--)
  {
   m=m*10+A[k]; 
  }
  for(j=0;j<=k;j++)
  { 
   m=m*10+A[j]; 
  } 
 }
 //If the next higher number needs to have greater number of digits.
 else
 {
  m=A[0];
  m=m*10+A[0];
  for(j=1;j<i;j++)
  { 
   m=m*10+A[j]; 
  } 
 }
 cout<<m<<endl;
 fflush(stdin);
 getchar();
 return 0; 
}
Input: 37723971
Output: 37727139