TCS codevite 2014 problem: Super ASCII String Checker

Problem : Super ASCII String Checker

In the Byteland country a string "S" is said to super ascii string if and only if count of each character in the string is equal to its ascii value.

In the Byteland country ascii code of 'a' is 1, 'b' is 2 ...'z' is 26.

Your task is to find out whether the given string is a super ascii string or not.

Input Format:

First line contains number of test cases T, followed by T lines, each containing a string "S".

Output Format:

For each test case print "Yes" if the String "S" is super ascii, else print "No"

Constraints:

1<=T<=100

1<=|S|<=400, S will contains only lower case alphabets ('a'-'z').

Sample Input and Output

SNo.	Input	Output
1	2 bba scca	Yes No

Explanation:

In case 1, viz. String "bba" -
The count of character 'b' is 2. Ascii value of 'b' is also 2.
The count of character 'a' is 1. Ascii value of 'a' is also 1.
Hence string "bba" is super ascii.

Solution:

#include<iostream>

using namespace std;

int c[26];

int main(){

    int t,len,flag=1;;

    string s;

    cin>>t;

    while(t--){

        cin>>s;

        len=s.length();

        for(int i=0;i<len;i++)

            c[int(s[i])-int('a')]++;

        for(int i=0;i<26;i++){

            if(!(c[i]==0 || c[i]==i+1))

                flag=0;

        }

        if(flag==1)

            cout<<"Yes\n";

        else

            cout<<"No\n";

        for(int i=0;i<26;i++)

            c[i]=0;

        flag=1;

    }

    return 0;

}

TCS codevite 2014 question with solution Matrix Rotations

Problem : Matrix Rotations

You are given a square matrix of dimension N. Let this matrix be called A. Your task is to rotate A in clockwise direction byS degrees, where S is angle of rotation. On the matrix, there will be 3 types of operations viz. 

1. Rotation

   Rotate the matrix A by angle S, presented as input in form of A S 

2. Querying

   Query the element at row K and column L, presented as input in form of Q K L

3. Updation

   Update the element at row X and column Y with value Z,  presented as input in form of U X Y Z

Print the output of individual operations as depicted in Output Specification

Input Format:

Input will consist of three parts, viz.
1. Size of the matrix (N)
2. The matrix itself (A = N * N)
3. Various operations on the matrix, one operation on each line. (Beginning either with A, Q or U)

-1 will represent end of input.

Note:

• Angle of rotation will always be multiples of 90 degrees only.
• All Update operations happen only on the initial matrix. After update all the previous rotations have to be applied on the updated matrix

Output Format:

For each Query operation print the element present at K-L location of the matrix in its current state.

Constraints:

1<=N<=1000

1<=Aij<=1000

0<=S<=160000

1<=K, L<=N

1<=Q<=100000

Sample Input and Output

SNo.	Input	Output
1	2 1 2 3 4 A 90 Q 1 1 Q 1 2 A 90 Q 1 1 U 1 1 6 Q 2 2 -1	3 1 4 6

Solution:

#include<iostream>

using namespace std;

int n,mat[1000][1000],initial[1000][1000];

int temp[1000][1000];

//void print();

void transpose();

void rotate(int);

int main(){

    int x,y,z;

    int total=0;

char c;

cin>>n;

for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        cin>>mat[i][j];

        initial[i][j]=mat[i][j];

}

}

while(true){

    cin>>c;

    if(c=='A'){

        cin>>x;

        rotate(x);

        total+=x;

    }

    else if(c=='Q'){

        cin>>x>>y;

        cout<<mat[x-1][y-1]<<endl;

    }

    else if(c=='U'){

            cin>>x>>y>>z;

        for(int i=0;i<n;i++){

            for(int j=0;j<n;j++)

                mat[i][j]=initial[i][j];

        }

        mat[x-1][y-1]=z;

        rotate(total);

        //print();

    }

    else

        break;

}

return 0;

}

void transpose(){

 for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        temp[j][n-i-1]=mat[i][j];

    }

 }

 for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        mat[i][j]=temp[i][j];

    }

 }

}

void rotate(int x){

int t=x/90;

t=t%4;

while(t--){

    transpose();

       // print();

}

}/*

void print(){

    cout<<"printing matrix\n";

for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

        cout<<mat[i][j]<<" ";

    }

    cout<<endl;

}

}*/

TCS codevite 2014 Question with solution

Problem : Online Communities - Even Groups

In a social network, online communities refer to the group of people with an interest towards the same topic. People connect with each other in a social network. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.

We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.

Input Format:

Input will consist of three parts, viz.

1. The total number of people on the social network (N)
2.Queries 

• C I J, connect I and J
• Q 0 0, print the number of communities with even member-count

-1 will represent end of input.

Output Format:

For each query Q, output the number of communities with even member-count

Constraints:

1<=N<=10^6

1<=I, J<=N

Sample Input and Output

SNo.	Input	Output
1	5 Q 0 0 C 1 2 Q 0 0 C 2 3 Q 0 0 C 4 5 Q 0 0 -1	0 1 0 1

Solution:

//Problem: Online communities- Even groups

#include<iostream>

using namespace std;

int comm[1000001],n;

void mergecom(int,int);

//void print();

int even(int);

int main(){

    int x,y,comNo=1;

    char c;

    cin>>n;

    while(true){

        cin>>c;

        if(c=='C'){

            cin>>x>>y;

            if(comm[x]==0 && comm[y]==0){

                comm[x]=comm[y]=comNo;

                comNo++;

            }

            else if(comm[x]==0){

                comm[x]=comm[y];

            }

            else if(comm[y]==0){

                comm[y]=comm[x];

            }

            else if(comm[x]>comm[y]){

                mergecom(comm[y],comm[x]);

                comNo--;

            }

            else if(comm[y]>comm[x]){

                mergecom(comm[x],comm[y]);

                comNo--;

            }

        }

        else if(c=='Q'){

            cin>>x>>y;

            cout<<even(comNo)<<endl;

        }

        else

            break;

    }

return 0;

}

void mergecom(int x,int y){

    for(int i=0;i<=n;i++){

        if(comm[i]==y)

            comm[i]=x;

        else if(comm[i]>y)

            comm[i]--;

    }

}

int even(int comNo){

int count =0,temp=0;

for(int i=1;i<comNo;i++){

    for(int j=0;j<=n;j++){

        if(comm[j]==i)

            temp++;

    }

    if(temp%2==0 && temp!=0){

        count++;

    }

    temp=0;

}

return count;

}

/*

void print(){

for(int i=0;i<=n;i++)

    cout<<i<<comm[i]<<" ";

cout<<endl;

}*/

Finding co-prime numbers

 Two integers a and b are said to be relatively prime or co-prime if the only positive integer that evenly divides both of them is 1. That is, the only common positive factor of the two numbers is 1. This is equivalent to their greatest common divisor being 1.



#include<stdio.h>
int gcd(int a,int b){
if(a%b==0)
return b;
else
return gcd(b,a%b);

}
int main(){
int n,i,count=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
if(gcd(n,i)==1)
count++;
}
printf("%d",count);
return 0;
}

stack program through array

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 50
int top=-1;
int stack[MAX];
int push(x)
{    if(top==MAX)
{
     printf("stack is full\n");
     return 0;
     }
     stack[top+1]=x;
     top++;
     return 1;
}
int pop()
{   if(top==-1)
{
    printf("stack is empty\n");
    getch();  
    exit(0);
}
    int temp;
    temp=stack[top];
    top--;
    return temp;
}
int main()
{
    int x,y;
    while(x!=0)
    {
    printf("enter 1 to push 2 to pop 0 to exit");
    scanf("%d",&x);
    if(x==1)
    {
            printf("enter data\n");
            scanf("%d",&y);
            push(y);
}
if(x==2)
{
        y=pop();
        printf(" %d poped\n",y);
        }
        }
        getch();
        }

C Program of Double Linked List

#include <stdio.h>
#include <malloc.h>

struct node
{
 struct node *prev;
 int info;
 struct node *next;
}*start;

main()
{
 int choice,n,m,po,i;
 start=NULL;
 while(1)
 {
  printf("1.Create List\n");
  printf("2.Add at begining\n");
  printf("3.Add after\n");
  printf("4.Delete\n");
  printf("5.Display\n");
  printf("6.Count\n");
  printf("7.Reverse\n");
  printf("8.exit\n");
  printf("Enter your choice : ");
  scanf("%d",&choice);
  switch(choice)
  {
   case 1:
   printf("How many nodes you want : ");
   scanf("%d",&n);
   for(i=0;i<n;i++)
   {
    printf("Enter the element : ");
    scanf("%d",&m);
    create_list(m);
   }
   break;
   case 2:
   printf("Enter the element : ");
   scanf("%d",&m);
   addatbeg(m);
   break;
   case 3:
   printf("Enter the element : ");
   scanf("%d",&m);
   printf("Enter the position after which this element is inserted : ");
   scanf("%d",&po);
   addafter(m,po);
   break;
   case 4:
   printf("Enter the element for deletion : ");
   scanf("%d",&m);
   del(m);
   break;
   case 5:
   display();
   break;
   case 6:
   count();
   break;
   case 7:
   rev();
   break;
   case 8:
   exit();
   default:
   printf("Wrong choice\n");
 }/*End of switch*/
   }/*End of while*/
}/*End of main()*/

create_list(int num)
{
 struct node *q,*tmp;
 tmp= malloc(sizeof(struct node));
 tmp->info=num;
 tmp->next=NULL;
 if(start==NULL)
 {
  tmp->prev=NULL;
  start->prev=tmp;
  start=tmp;
 }
 else
 {
  q=start;
  while(q->next!=NULL)
   q=q->next;
  q->next=tmp;
  tmp->prev=q;
 }
}/*End of create_list()*/

addatbeg(int num)
{
 struct node *tmp;
 tmp=malloc(sizeof(struct node));
 tmp->prev=NULL;
 tmp->info=num;
 tmp->next=start;
 start->prev=tmp;
 start=tmp;
}/*End of addatbeg()*/

addafter(int num,int c)
{
 struct node *tmp,*q;
 int i;
 q=start;
 for(i=0;i<c-1;i++)
 {
  q=q->next;
  if(q==NULL)
  {
   printf("There are less than %d elements\n",c);
   return;
  }
 }
 tmp=malloc(sizeof(struct node) );
 tmp->info=num;
 q->next->prev=tmp;
 tmp->next=q->next;
 tmp->prev=q;
 q->next=tmp;
}/*End of addafter() */

del(int num)
{
 struct node *tmp,*q;
 if(start->info==num)
 {
  tmp=start;
  start=start->next;  /*first element deleted*/
  start->prev = NULL;
  free(tmp);
  return;
 }
 q=start;
 while(q->next->next!=NULL)
 {
  if(q->next->info==num)     /*Element deleted in between*/
  {
   tmp=q->next;
   q->next=tmp->next;
   tmp->next->prev=q;
   free(tmp);
   return;
  }
  q=q->next;
 }
 if(q->next->info==num)    /*last element deleted*/
 {  tmp=q->next;
  free(tmp);
  q->next=NULL;
  return;
 }
 printf("Element %d not found\n",num);
}/*End of del()*/

display()
{
 struct node *q;
 if(start==NULL)
 {
  printf("List is empty\n");
  return;
 }
 q=start;
 printf("List is :\n");
 while(q!=NULL)
 {
  printf("%d ", q->info);
  q=q->next;
 }
 printf("\n");
}/*End of display() */

count()
{  struct node *q=start;
 int cnt=0;
 while(q!=NULL)
 {
  q=q->next;
  cnt++;
 }
 printf("Number of elements are %d\n",cnt);
}/*End of count()*/

rev()
{
 struct node *p1,*p2;
 p1=start;
 p2=p1->next;
 p1->next=NULL;
 p1->prev=p2;
 while(p2!=NULL)
 {
  p2->prev=p2->next;
  p2->next=p1;
  p1=p2;
  p2=p2->prev; /*next of p2 changed to prev */
 }
 start=p1;
}/*End of rev()*/

Factorial of a number using resursion

#include<stdio.h>
#include<conio.h>

int fact(int);
main()
{int y,n;
printf("Enter a number to find its factorial\n");
scanf("%d",&n);

y=fact(n);
printf("factorial = %d",y);
getch();
 }
 int fact(int x)
 {
  if(x>1)
  return x*fact(x-1);
  else
  return 1;

}