CareerCup

You can use binary search and insertion for each element generated. The O(log n) will enable you for minimum memory utilization assuming only half array will be in memory for each computation. We can publish the array to the disk. Keeping the array in sorted order can help in generating a stream for the same and printing while fetching from any disk storage.

You can use binary sort while fetching and inserting the number in a array. the final print would just print the array from first to last element. Complexity would be O(log n) for searching and inserting. and O(n) for printing the final array.

We need to provide largest submatrix not largest square submatrix. Hence we need to check all sub-matrixes possible and it can be done by
geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

push the open parenthesis and the operators and check the top element on seeing a closing parenthesis. If it is open one we have duplicate.

int check(char s[])
{
    int i=0;
    char ch;
    while(s[i]!='\0')
    {
       if(s[i]=='(' || s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')
          push(s[i]);
       else if(s[i]==')')
       {
            ch=pop();
            if(ch=='(')
               return 1;
            while((ch=pop())!='(')
                ;
       }
       i++;
    }
    return 0;
}

Its simple to finding kth element in the merged array in logarithmic time.
take pivot in two arrays such that sum of pivot 1 + pivot 2 =n.
compare the pivot elements and search the correcponding array half if not equal

int getk(int a[],int l1,int m,int b[],int l2,int n,int k)
{
    if(m<=0 || k<=0 || k<=0 || k>(m+n))
       return -1;
    
    int i = m * (k-1) / (m+n);
    int j = k-i-1;
    
    int ai_1 = (i==0)?-100:a[l1 + i-1];
    int bj_1 = (j==0)?-100:b[l2 + j-1];
    int ai = (i==m)?100:a[l1 + i];
    int bj = (j==n)?100:b[l2 + j];
    
    if(bj_1<=ai && ai<=bj)
      return ai;
    if(ai_1<=bj && bj<=ai)
      return bj;
    
    if(ai<bj)
      return getk(a,l1+i+1,m-i-1,b,l2,j,k-i-1);
    return getk(a,l1,i,b,l2+j+1,n-j-1,k-j-1);
}

int getmed(int a[],int m,int b[],int n)
{
    if((m+n)%2!=0)
       return getk(a,0,m,b,0,n,(m+n)/2+1);
    return (getk(a,0,m,b,0,n,(m+n)/2) + getk(a,0,m,b,0,n,(m+n)/2+1))/2;
}

Do a reverse in order traversal to get the desired output.

There is an excellent, and very short random generator : the XORShift. It passes random generator Diehard tests, and is very concise.
en.wikipedia.org/wiki/Xorshift

You will need to have a stack and a completed array. completed array denotes if you have seen both the children of the tree.
Now push a node in the stack and increment its children count. when the completed count is 2 you can pop out the node.
The code can be written as:

void printpath()
{
     int i=0;
     for(i=0;i<in;i++)
        printf("%d\t",stack[i]->val);
     printf("\n");
}

void allpaths(struct tnode *root)
{
     int done=0;
     int completed[100];
     int i=0;
     for(i=0;i<100;i++)
        completed[i]=0;
     struct tnode *cur = root;
     while(done!=1)
     {
        if(cur!=NULL)
        {
           push(cur);
           completed[cur->val]++;
           cur = cur->left;
        }
        else
        {
            cur = front();
            while(cur != NULL && completed[cur->val]==2)
            {
               if(cur->left==NULL && cur->right==NULL)
                  printpath();
               pop();
               cur = front();
            }
            if(cur!=NULL)
            {
               completed[cur->val]++;
               cur = cur->right;
            }
            else
               done =1 ;
        }
     }
}

void paths(struct tnode *root,int num)
{
    int done=0;
    int complete[100];
    int i=0;
    for(i=0;i<100;i++)
       complete[i]=0;
    struct tnode *cur = root;
    while(done != 1)
    {
       if(cur!=NULL)
       {
          push(cur);
          if(cur->val==num)
             break;
          complete[cur->val]++;
          cur = cur->left;
       }
       else
       {
           cur = front();
           while(cur != NULL && complete[cur->val]==2)
           {
              pop();
              cur = front();
           }
           if(cur != NULL)
           {
              complete[cur->val]++;
              cur =  cur->right;
           }
           else
              done = 1;
       }
    }
    if(done==0)
       printpath();
}

where we have to find path from root to num.

Can you please post an example to understand the question

In case of complete bst we can utilize the property of having n depth and 2^n-1 elements as :

int getnode(struct tnode *root,int n,int k)
{
    if(root==NULL)
       return -1;
    if(n/2 +1 == k)
       return root->val;
    if(n/2 + 1 > k)
       return getnode(root->left,n/2,k);
    return getnode(root->right,n/2,k-n/2-1);
}

n here is total nodes in tree

Not possible with a balanced bst. It is impossible to decide the path at root which to take in this case. It needs to be a complete bst instead for a O(lgn) solution.

int isvalid(int a[],int ind,int data)
{
    int i=ind-1;
    while(i>=0 && a[i]!=data)
       i--;
    if(i<0 || ind-i-1==data)
       return 1;
    return 0;
}

void getarray(int a[],int ind,int n,int val[])
{
     if(ind==2*n)
     {
        
        int i=0;
        for(i=1;i<=n;i++)
        {
           if(val[i]==0)
              return;
        }
        for(i=0;i<2*n;i++)
           printf("%d\t",a[i]);
        printf("\n");
        return;
     }
     int i=0;
     for(i=1;i<=n;i++)
     {
        if(isvalid(a,ind,i))
        {
           a[ind]=i;
           val[i]++;
           getarray(a,ind+1,n,val);
           val[i]--;
        }
     }
}

The list represents students standing in a cirle. Hence the final output should also remain circular. The head can change anywhere but the pattern needs to be the same...i.e. rgyb can be gybr or ybrg etc...

1. using brute force will give O(n2) complexity.
2. sorting and comparing will give O(nlogn) complexity.
3. Using one array to se a bit vector and other to check if bit is set will give O(n) complexity.

Hey, I was asked to write the code too. Can you please clarify your algo bit more.

void max(int a[],int n)
{
     int i=0,sum=0,max=0,end=0;
     for(i=0;i<n;i++)
     {
         sum = sum+a[i];
         if(sum>max)
         {
            max=sum;
            end=i;
         }
         if(sum<0)
            sum=0;
     }
     printf("Maximum Sum is %d\n",max);
     while(max>0)
     {
         printf("%d\t",a[end]);
         max = max-a[end];
         end--;
     }
     printf("\n");
}

struct tnode *addnode(int num)
{
       struct tnode * root = (struct tnode *) malloc(sizeof(struct tnode));
       root->val=num;
       root->left = NULL;
       root->right=NULL;
       return root;
}

struct tnode * create(int a[],int n)
{
     int i=0;
     while(a[i]!=-1)
        i++;
     struct tnode * root = addnode(i);
     push(root);
     struct tnode * temp = pop();
     while(temp!=NULL)
     {
        for(i=0;i<n;i++)
        {
           if(a[i]==temp->val)
           {
              if(temp->left==NULL)
              {
                 temp->left = addnode(i);
                 push(temp->left);
              }
              else
              {
                 temp->right = addnode(i);
                 push(temp->right);
              }
           }
        } 
        temp=pop();
     }
     return root;
}

void getbfs(struct tnode *root)
{
     int a[100][100],ind=0,in=0;
     struct tnode *dummy = addnode(-1);
     push(root);
     push(dummy);
     struct tnode *temp = pop();
     while(temp!=NULL)
     {
        while(temp!=dummy)
        {
           a[ind][in++]=temp->val;
           if(temp->left!=NULL)
              push(temp->left);
           if(temp->right!=NULL)
              push(temp->right);
           temp=pop();
        }
        if(temp==dummy)
        {
           a[ind][in]=-1;
           ind++;
           in=0;
        }
        temp=pop();
        if(temp!=NULL)
           push(dummy);
     }
     while(ind-->0)
     {
        in=0;
        while(a[ind][in]!=-1)
        {
           printf("%d\t",a[ind][in]);
           in++;
        }
        printf("\n");
     }
}

Its about maximum times an interval overlaps

void divide(int num,int denom)
{
     if(denom==0)
        return;
     int mask=1;
     int q=0;
     while(denom <= num)
     {
         denom = denom<<1;
         mask = mask<<1;
     }
     while(mask > 1)
     {
         mask = mask>>1;
         denom = denom>>1;
         if(num > denom)
         {
           num = num - denom;
           q = q|mask;
         }
     }
     printf("Quotient is %d and remainder is %d\n",q,num);
}

void process(char s[])
{
     int i=0,flag=1;
     while(s[i]!='\0')
     {
         if(flag==1 && s[i]==' ')
         {
            i++;
            continue;
         }
         if(flag==1)
            toupper(&s[i]);
         else
            tolower(&s[i]);
         putchar(s[i]);
         if(flag==1)
            flag=0;
         if(s[i]=='.')
         {
            putchar('\n');
            flag=1;
         }
         i++;
     }
     putchar('\n');
}

void longest(int a[][M])
{
     int i=0,j=0;
     int max=0,row=-1,col=-1,count=0;
     for(j=0;j<M;j++)
     {
        count=0;
        for(i=0;i<N;i++)
        {
            if(a[i][j]==1)
               count++;
            else
            {
                if(count>max)
                {
                   max = count;
                   row = j;
                }
                count =0;
            }
        }
        if(count>max)
        {
            max = count;
            row = j;
        }
     }
     for(i=0;i<N;i++)
     {
        count=0;
        for(j=0;j<M;j++)
        {
            if(a[i][j]==1)
               count++;
            else
            {
                if(count>max)
                {
                   max = count;
                   col = i;
                }
                count =0;
            }
        }
        if(count>max)
        {
            max = count;
            col = i;
        }
     }
     if(col==-1)
     {
        printf("Row is %d and sequence count is %d\n",row,max);
        count=0;
        for(i=0;i<N;i++)
        {
           if(a[i][row]==1)
              count++;
           else
              count =0;
           if(count==max)
              col=i;
        }
        printf("Sequence is from [%d,%d] to [%d,%d]\n",col-max+1,row,col,row);
     }
     else
     {
        printf("Column is %d and sequence count is %d\n",col,max);
        count=0;
        for(i=0;i<M;i++)
        {
           if(a[col][i]==1)
              count++;
           else
              count =0;
           if(count==max)
              row=i;
        }
        printf("Sequence is from [%d,%d] to [%d,%d]\n",col,row-max+1,col,row);
     }
}

int bfs(int graph[][V],int src,int dest,int parent[])
{
    int visited[V];
    int i=0;
    for(i=0;i<V;i++)
       visited[i]=0;
    push(src);
    parent[src]=-1;
    visited[src]=1;
    int temp = pop();
    while(temp!=-1)
    {
        for(i=0;i<V;i++)
        {
           if(visited[i]==0 && graph[temp][i]>0)
           {
              visited[i]=1;
              push(i);
              parent[i]=temp;
           }
        }
        temp=pop();
    }
    return visited[dest];
}

void dfs(int graph[][V],int src,int visited[])
{
     visited[src]=1;
     int i=0;
     for(i=0;i<V;i++)
     {
        if(visited[i]==0 && graph[src][i]>0)
           dfs(graph,i,visited);
     }
}

int getmin(int graph[][V],int src,int dest)
{
    int res[V][V];
    int i=0,j=0;
    for(j=0;j<V;j++)
    {
       for(i=0;i<V;i++)
          res[i][j] = graph[i][j];
    }
    int parent[V];
    int flow=1000;
    int mincap=0;
    while(bfs(res,src,dest,parent))
    {
        flow = 1000;
        int v = dest;
        while(v!=src)
        {
           int u = parent[v];
           if(flow>res[u][v])
              flow = res[u][v];
           v=u;
        }
        v = dest;
        while(v!=src)
        {
           int u = parent[v];
           res[u][v] = res[u][v]-flow;
           res[v][u] = res[v][u]+flow;
           v = u;
        }
        mincap = mincap + flow;
    }
    int visited[V];
    for(i=0;i<V;i++)
       visited[i]=0;
    dfs(res,src,visited);
    for(i=0;i<V;i++)
    {
       for(j=0;j<V;j++)
       {
           if(visited[i]==1 && visited[j]==0 && graph[i][j]>0)
              printf("%d---->%d\t",i,j);
       }
    }
    printf("\n");
    return mincap;
}

void elements(int a[][N],int x,int y,int col,int *n)
{
     if(x<0 || x>=N || y<0 || y>=N || a[x][y]!=col || a[x][y]==-1)
        return;
     (*n)++;
     a[x][y]=-1;
     printmatrix(a);
     elements(a,x+1,y,col,n);
     elements(a,x-1,y,col,n);
     elements(a,x,y+1,col,n);
     elements(a,x,y-1,col,n);
}

void getmax(struct ele a[])
{
     int i=0,j=0;
     struct temp b[2*N];
     for(i=0;i<N;i++)
     {
        b[j].time = a[i].start;
        b[j++].c = 's';
        b[j].time = a[i].end;
        b[j++].c = 'e';
     }
     sort(b,0,2*N-1);
     int count=0,start=0,max=0;
     for(i=0;i<2*N;i++)
     {
        if(b[i].c == 's')
           count++;
        if(b[i].c == 'e')
           count--;
        if(max<count)
        {
           max = count;
           start = b[i].time;
        }
     }
     int begin=100,end=0;
     for(i=0;i<N;i++)
     {
        if(start>a[i].start && start <a[i].end)
        {
           if(a[i].start<begin)
           {
              begin = a[i].start;
              end = a[i].end;
           }
        }
     }
     printf("Max overlapping interval is (%d,%d) and max overlap is %d\n",begin,end,max);
}

It will not work as its answer is [8,10]...while the correct answer should be [2,9]

int check(char ch[][M],int i,int j,char s[],int ind)
{
    if(i>=N || j>=M || ch[i][j]!=s[ind] || ch[i][j]=='-')
       return 0;
    if(ind==strlen(s)-1)
       return 1;
    return check(ch,i+1,j,s,ind+1) + check(ch,i,j+1,s,ind+1) + check(ch,i+1,j+1,s,ind+1);
}

void swaps(int a[],int b[],int n)
{
     int i=1;
     int hash[100];
     for(i=1;i<=n;i++)
        hash[a[i]]=i;
     for(i=1;i<=n;i++)
        printf("%d--->%d\n",i,hash[i]);
     int count=0;
     i=1;
     while(i<=n)
     {
        if(b[i]==a[i])
          i++;
        else
        {
           int temp = hash[b[i]];
           b[i]=b[i]^b[temp];
           b[temp]=b[i]^b[temp];
           b[i]=b[i]^b[temp];
           count++;
        }
     }
     printf("Count is %d\n",count);
}

can you please elaborate on this.

it will give max count not the interval

I think what we need here is all possible subsets which sum to a particular value say s.
In case of all positive values we can sort and ignore values >s and get subsets of remaining values which sum to s.
In case of both negative and positive values we need to go for subsets of whole array and sorting would be irrelevant in this case.

void permute(char s[],int left,int n)
{
if(left>=n)
{
printf("%s\n",s,left,n);
return;
}
int k=0;
for(k=left;k<n;k++)
{
swap(s,left,k);
permute(s,left+1,n);
swap(s,left,k);
}
}

Same code ... just marking visited flag to avoid repeated usage of that.

int check(char a[][N],int i,int j,char s[],int ind,int n)
{
    if(ind==n)
       return 1;
    if(i<0 || j<0 || i>=M || j>=N || a[i][j] != s[ind] || a[i][j]=='-')
       return 0;
    a[i][j]='-';
    return check(a,i+1,j,s,ind+1,n) || check(a,i-1,j,s,ind+1,n) || check(a,i,j+1,s,ind+1,n) || check(a,i,j-1,s,ind+1,n);
    a[i][j]=s[ind];
}

One solution can be we get the span of ith day by checking if any j<i exists such that a[j]<a[i].
If so, in that case span[i]=span[j]+1 else it will be 0.

void getspan(int a[],int n)
{
     int span[100];
     int i=0,j;
     span[0]=0;
     for(i=1;i<n;i++)
     {
        j=i-1;      
        while(j>=0 && a[j]>=a[i])
           j--;
        if(j==-1)
           span[i]=0;
        else
           span[i]=span[j]+1;
     }
     for(i=0;i<n;i++)
        printf("%d\t",span[i]);
     printf("\n");
}

void findlongest(struct tnode *root,int a[],int ind,int level,int *max,int path[])
{
if(root==NULL)
{
if(level>*max)
{
int i=0;
for(i=0;i<ind;i++)
path[i]=a[i];
*max=level;
}
return;
}
a[ind]=root->val;
findlongest(root->left,a,ind+1,level+1,max,path);
findlongest(root->right,a,ind+1,level+1,max,path);
}

int main()
{
int i,num;
struct tnode *root=NULL;
for(i=0;i<N;i++)
{
scanf("%d",&num);
root=addnode(root,num);
}
int a[100],leftpath[100],rightpath[100];
num=0;
findlongest(root->left,a,0,0,&num,leftpath);
while(num>0)
printf("%d\t",leftpath[--num]);
printf("%d\t",root->val);
num=0;
findlongest(root->right,a,0,0,&num,rightpath);
for(i=0;i<num;i++)
printf("%d\t",rightpath[i]);
printf("\n");
getch();
return 0;
}

int mina1[100];
int n1;
int mina2[100];
int n2;

void getsub(int a[],int n,int a1[],int ind1,int a2[],int ind2,int sum1,int sum2,int *min)
{
     if(n==0)
     {
        if(sum1>sum2)
        {
           if(sum1-sum2<*min)
           {
              *min=sum1-sum2;
              int i=0;
              for(i=0;i<ind1;i++)
                 mina1[i]=a1[i];
              n1=ind1;
              for(i=0;i<ind2;i++)
                 mina2[i]=a2[i];
              n2=ind2;
           }
        }
        else
        {
           if(sum2-sum1<*min)
           {
              *min=sum2-sum1;
              int i=0;
              for(i=0;i<ind1;i++)
                 mina1[i]=a1[i];
              n1=ind1;
              for(i=0;i<ind2;i++)
                 mina2[i]=a2[i];
              n2=ind2;
           }
        }
        return;
     }
     a1[ind1]=a[n-1];
     getsub(a,n-1,a1,ind1+1,a2,ind2,sum1+a[n-1],sum2,min);
     a2[ind2]=a[n-1];
     getsub(a,n-1,a1,ind1,a2,ind2+1,sum1,sum2+a[n-1],min);
}

For n intervals create n queues. Fill queue with the elements in between intervals. Find the minimum of all queue first elements and continue till we get ith.
Ex--5-10 and 8-12
q1 : 5,6,7,8,9,10
q2: 8,9,10,11,12
min element array = 5,6,7,8,8,9,9,10,10,11,12

geeksforgeeks.org/find-first-non-repeating-character-stream-characters/

Use hashmap to uniquely identify keys in place of repeated array.

void getmin(int a[],int n,int num)
{
     int i=0;
     int b[100];
     push_back(0);
     for(i=1;i<n;i++)
     {
        while(front()!=-100 && front() <= i-num)
              pop_front();
        while(front()!=-100 && a[back()]>a[i])
              pop_back();
        push_back(i);
        if(i>=num-1)
           b[i-num+1]=a[front()];
     }
     for(i=0;i<n-num+1;i++)
        printf("%d\t",b[i]);
     printf("\n");
}

en.wikipedia.org/wiki/Longest_repeated_substring_problem

leetcode.com/2010/11/finding-minimum-window-in-s-which.html...modify the solution for words instead of chars

void formatsize(int size)
{
     int dig=0;
     int pow=1;
     int num=size;
     while(num>0)
     {
        num=num/10;
        dig++;
        pow=pow*10;
     }
     num=size%pow;
     size=num;
     dig=0;
     pow=1;
     while(num>0)
     {
        num=num/10;
        dig++;
        pow=pow*10;
     }
     num=size;
     if(dig<=3)
     {
        printf("%dB\n",num);
        return;
     }
     pow=pow/100;
     if(pow<=1000)
        pow=1000;
     else if (pow<=1000000)
        pow=1000000;
     double n=(double)size/pow;
     if(pow==1000)
        printf("%.1fK\n",n);
     else if(pow==1000000)
        printf("%.1fM\n",n);
}

void getmin(int sum,int a[],int n,int count,int *min)
{
    if(n==0 || sum<0)
       return;
    if(sum==0)
    {
       if(count<*min)
          *min=count;
       return;
    }
    if(sum>=a[n-1])
       getmin(sum-a[n-1],a,n,count+1,min);
    getmin(sum,a,n-1,count,min);
}

int max(int a,int b)
{
    if(a>b)
      return a;
    return b;
}

int maxvalue(int val[],int wt[],int W,int n)
{
    if(W==0 || n==0)
       return 0;
    if(wt[n-1]>W)
       return maxvalue(val,wt,W,n-1);
    return max(val[n-1]+maxvalue(val,wt,W-wt[n-1],n),maxvalue(val,wt,W,n-1));
}

struct tnode *rightmost(struct tnode *root)
{
       while(root->right!=NULL)
          root = root->right;
       return root;
}

struct tnode *getpre(struct tnode *root,struct tnode *node,struct tnode *prev)
{
       if(root==NULL)
          return NULL;
       if(root==node)
       {
          if(root->left!=NULL)
             return rightmost(root->left);
          return prev;
       }
       struct tnode *temp=getpre(root->left,node,prev);
       if(temp==NULL)
          return getpre(root->right,node,root);
       return temp;
}

void findbelow(struct tnode *root,int level,int k)
{
     if(root==NULL)
        return;
     if(level==k)
     {
        printf("%d\t",root->val);
        return;
     }
     findbelow(root->left,level+1,k);
     findbelow(root->right,level+1,k);
}

void findabove(struct tnode *root,struct tnode *node,int level,int k)
{
     static int vector=0;
     if(root==NULL)
        return;
     findabove(root->left,node,level+1,k);
     findabove(root->right,node,level+1,k);
     if(root==node)
        vector = vector | 1<<level;
     if(vector & 1<<(level+k))
     {
        vector = vector ^ 1<<(level+k);
        printf("%d\t",root->val);
     }
}

int check(struct tnode *root,int min,int max)
{
    if(root==NULL)
       return 1;
    if(root->val>=min && root->val<max)
       return check(root->left,min,root->val) && check(root->right,root->val,max);
    return 0;
}

Solution only for + and * operator

void evaluate(char s[])
{
     int i=0;
     int dig=1;
     int num=0;
     char c;
     while(s[i]!='\0')
     {
        if(s[i]<='9' && s[i]>='0')
        {
           num = num*dig + s[i]-'0';
           dig=dig*10;
        }
        else if(s[i]=='+' || s[i]=='*')
        {
             if(num!=0)
             {
                vpush(num);
                num=0;
                dig=1;
             }
             if(s[i]=='+')
             {
                c=opop();
                if(c=='*')
                {
                   int num1=vpop();
                   int num2=vpop();
                   vpush(num1*num2);
                }
             }
             opush(s[i]);
        }
        i++;
     }
     if(num!=0)
     {
        vpush(num);
        num=0;
        dig=1;
     }
     while(oind>0)
     {
        c=opop();
        int num1=vpop();
        int num2=vpop();
        if(c=='+')
           vpush(num1+num2);
        else
           vpush(num1*num2);
     }
     printf("Answer is %d\n",vpop());
}

For subset code can be

void printarray(int a[],int start,int end)
{
     int i=0;
     for(i=start;i<=end;i++)
        printf("%d\t",a[i]);
     printf("\n");
}

int power(int a,int n)
{
    while(--n>0)
       a=a*2;
    return a;
}

void getsubset(int a[],int n)
{
     int i=0,j=0;
     int set[100];
     int ind=0;
     int count = power(2,n);
     int sum=0;
     for(i=0;i<count;i++)
     {
        sum=0;
        ind=0;
        for(j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
               sum = sum + a[j];
               set[ind++]=a[j];
            }
        }
        if(sum==0)
           printarray(set,0,ind-1);
     }
}

As per example given..the code can be

void printarray(int a[],int start,int end)
{
     int i=0;
     for(i=start;i<=end;i++)
        printf("%d\t",a[i]);
     printf("\n");
}

void getsub(int a[],int n)
{
     int i=0,j=0;
     int b[100];
     b[0]=a[0];
     for(i=1;i<n;i++)
        b[i]=b[i-1]+a[i];
     for(i=0;i<n;i++)
     {
        if(b[i]==0)
        {
           printarray(a,0,i);
           continue;
        }
        for(j=0;j<i;j++)
        {
           if(b[j]==b[i])
              printarray(a,j+1,i);
        }           
     }
}

char toupper(char c)
{
     if(c>='a' && c<='z')
        return c-32;
     return c;
}

void out(char s[])
{
     int i=0,count=0;
     while(s[i]!='\0')
     {
        if(count==0)
        {
           printf("%c",toupper(s[i]));
           count++;
        }
        else
        {
            if(toupper(s[i])==toupper(s[i-1]))
               count++;
            else
            {
                printf("%d",count);
                count=0;
                i--;
            }
        }
        i++;
     }
     printf("%d\n",count);
}