Search String S2 in S1 Character Matrix

Given two strings S1 and S2, form a R*C matrix with the string S1 (You may repeat the string S1 to fill in the rest of the matrix, if length of S1 is less than R*C). Then search for the string S2 along rows from left to right or along columns from top to bottom) and print the number of occurrence of S2.

Input Format:

The first line contains R and C separated by a space. The second line contains S1. The third line contains S2.

Output Format:

The first line contains the integer value denoting the number of occurrence of S2 in the character matrix formed.

Boundary Conditions:

2 <= R, C <= 100

2 <= Length of S1 <= 10000

2 <= Length of S2 <= 200

Example Input/Output 1:

Input:

5 4

managermetuatten

man

Output:

3

Explanation: 
The 5*4 character matrix formed using S1 is mana germ etua tten mana man can be found in 1st row from left to right and in 4th column from top to bottom. Then it is also found in 5th row. Hence the overall occurrence count is 2.

Solution:

#include <iostream>

using namespace std;

int main()

{

  int n,m,i,j,f,c=0;

  string s,t;

  cin>>n>>m>>s>>t;

  int k=0,l=s.size(),p=t.size();

  char a[n][m];

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

   for(j=0;j<m;j++,k=k%l)

    a[i][j]=s[k++];

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

   for(j=0;j<m;j++)

   {

       if(j+p-1<m)

         {

             f=0;

             for(k=0;k<p;k++)

               if(a[i][j+k]!=t[k])

                    f=1;

             if(f==0)

               c++;

         }

        if(i+p-1<n)

         {

             f=0;

             for(k=0;k<p;k++)

              if(a[i+k][j]!=t[k])

                  f=1;

              if(f==0)

                c++;

         }

   }

  cout<<c;

}

Read More

Print Matrix - Diagonal Zig Zag

An R*C matrix is passed as the input to the program. The program must print the values in zig-zag order diagonally. (Please refer Example Input/Output section for more details).

Input Format:

The first line contains R and C separated by a space. Next R lines contain C values separated by a space.

Output Format:

The first line contains all R*C elements in zig-zag order diagonally, with the elements separated by a space.

Boundary Conditions: 2 <= R, C <= 100

Example Input/Output 1:

Input:

3 3

1 2 3

4 5 6

7 8 9

Output:

1 2 4 7 5 3 6 8 9

Example Input/Output 2:

Input:

3 7

1 2 3 4 5 6 7

8 9 1 2 3 4 5

6 7 8 9 1 2 3

Output:

1 2 8 6 9 3 4 1 7 8 2 5 6 3 9 1 4 7 5 2 3

Solution:

#include <iostream>

using namespace std;

int main()

{

 int n,m,i,j,k,f=1;

 cin>>n>>m;

 int a[n][m];

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

  for(j=0;j<m;j++)

    cin>>a[i][j];

 for(i=0,j=0,k=0;k<n*m;)

 {

     if(f)

     {

         for(;i>=0&&j<m;i--,j++)

         {

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

             k++;

         }

         if(i<0&&j<=m-1)

           i=0;

         if(j==m)

           i+=2,j--;

     }

     else

     {

        for(;j>=0&&i<n;j--,i++)

        {

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

            k++;

        }

        if(j<0&&i<=n-1)

          j=0;

        if(i==n)

          j+=2,i--;

     }

    f=!f;

 }

}

Read More

Number to Words - CTS3

You are working in a bank. Given a cheque, you have been asked to verify if the amount in words and amount in numbers are the same. Your task is to write a C program to convert the amount (i.e, the number) to words.

Input:

Input consists of an integer denoting the amount.

Output:

Print the given integer amount in words as a string.

Note:

All aplahabets are in lower case only.

The given amount is less than ten lakhs.

Sample:

1] Input: 12

    Output: twelve

2] Input: 1098

    Output: one thousand and ninety eight

3] Input: 975421

    Output: nine lakh seventy five thousand four hundred and twenty one

Solution:

#include <iostream>

using namespace std;

const string EMPTY = "";

string X[] = { EMPTY, "One ", "Two ", "Three ", "Four ", "Five ",

                                       "Six ", "Seven ", "Eight ", "Nine ", "Ten ", "Eleven ",

                                       "Twelve ", "Thirteen ", "Fourteen ", "Fifteen ",

                                       "Sixteen ", "Seventeen ", "Eighteen ", "Nineteen " };

string Y[] = { EMPTY, EMPTY, "Twenty ", "Thirty ", "Forty ", "Fifty ",

                "Sixty ", "Seventy ", "Eighty ", "Ninety " };

string convert2digit(int n, string suffix)

{

    if (n == 0)

        return EMPTY;

          if (n > 19)

                   return Y[n / 10] + X[n % 10] + suffix;

          else

                   return X[n] + suffix;

}

string numberToWords(unsigned long long int n)

{

          string res;

          res = convert2digit((n % 100), EMPTY);

          if (n > 100 && n % 100)

                   res = "and " + res;

          res = convert2digit(((n / 100) % 10), "Hundred ") + res;

          res = convert2digit(((n / 1000) % 100), "Thousand ") + res;

          res = convert2digit(((n / 100000) % 100), "Lakh, ") + res;

          res = convert2digit((n / 10000000) % 100, "Crore, ") + res;

          res = convert2digit((n / 1000000000) % 100, "Billion, ") + res;

          return res;

}

int main()

{

    int n;

    cin>>n;

          cout << numberToWords(n) << endl;

          return 0;

}

Read More

Split String & Sort

An even length string S is passed as the input. The program must split the string into two parts S1 and S2 and sort them in ascending order.

Input Format:

The first line contains S.

Output Format:

Two lines containing S1 and S2 sorted in ascending order.

Boundary Conditions: 2 <= Lenngth of S <= 10000

Example Input/Output 1:

Input:

manage

Output:

age man

Solution:

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

 string s,a[2];

 cin>>s;

 a[0]=s.substr(0,s.size()/2);

 a[1]=s.substr(s.size()/2,s.size());

 sort(a,a+2);

 cout<<a[0]<<endl<<a[1];

}

Read More

Four Strings Rectangle - 2 Diff length

Four strings out of which two have the same length L1 and the remaining two have the same length L2 are passed as the input to the program. The four strings must be printed in a L1*L2 rectangular matrix shape as shown in the example input/output. L1 >= L2 and a string with L1 must appear on the top of the rectangle. The string which is on the top with length L1 will always be the first string in the input. Other three strings can occur in a random order in the input. The sequence of the string can be identified by the fact that the last letter of a string will be the first letter of another string (and you can safely assume the last letter will not occur more than once).

Input Format:

The first line contains the string which represents the top of the rectangular matrix. The next three lines will contain the remaining the three string values which can represent the right, left and bottom side of the rectangle, but not necessarily in the same order.

Output Format:

The L1*L2 rectangular matrix with these four strings as it's sides as described in the Example Input/Output.

Boundary Conditions:

 3 <= L1, L2 <= 100 L1 >= L2

Example Input/Output 1:

Input:

MANAGE

SUM

TAURUS

EAT

Output:

MANAGE

U****A

SURUAT

Solution-1:

#include <bits/stdc++.h>

#include <string>

using namespace std;

int main(int argc, char** argv)

{

    string s[4];

    cin>>s[0]>>s[1]>>s[2]>>s[3];

    string l,r,m;

    for(int i=1;i<4;i++)

    {

        if(s[0][0]==s[i][s[i].length()-1])

        {

        l=s[i];

        s[i]="*";

        }

        else if(s[0][s[0].length()-1]==s[i][0])

        {

            r=s[i];

            s[i]="*";

        }

    }

    for(int i=1;i<4;i++)

    {

        if(s[i]!="*")

        m=s[i];

    }

    cout<<s[0]<<endl;

    int x=l.length()-2,y=1;

    for(int i=1;i<l.length()-1;i++)

    {

        for(int j=0;j<s[0].length();j++)

        {

            if(j==0)

            {

                cout<<l[x];x--;

            }

            else if(j==s[0].length()-1)

            {

                cout<<r[y];y++;

            }

            else

            cout<<"*";

        }

        cout<<endl;

    }

    reverse(m.begin(),m.end());

    cout<<m;

}

Read More

Maximum repeated Character - CTS2

Find the character which appeared the maximum time. If you have multiple character as result return the first character in that list. 

Sample Input & Output:

Input: "helloworld"

Output: 'l'

Input: "yehaha"

Output: 'h

Note: Don’t use scanf, cin or Scanner class. Use command line arguments to get inputs

Solution:

#include<iostream>

#include <map>

using namespace std;

int main(int x,char *v[])

{

 string t,s=v[1];

 map<char,int> m;

 int c=0;

 char ch;

 for(int i=0;i<s.size();i++)

  if(++m[s[i]]==1)

   t+=s[i];

 for(int i=0;i<t.size();i++)

  if(c<m[t[i]])

  {

   c=m[t[i]];

   ch=t[i];

  }

  cout<<ch;

}

Read More

String Numbers Sum - CTS2

Given two numbers, which are given as Strings, return us a string which is the sum of these two numbers. Please DO NOT convert to integers using inbuilt string functions.

Sample Input & Output:

Input: 145 39

Output: 184

Note: Don’t use scanf, cin or Scanner class. Use command line arguments to get inputs

Solution:

#include <stdio.h>

#include <string.h>

int main(int argc, char *argv[])

{

  printf("%d",atoi(argv[1])+atoi(argv[2]));

}

Read More

Trains and Platforms - CTS2

Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.

Input Format:

The first line of input consists of an integer N that represents total number of trains.

The next N lines contain arrival Ta[i] and departure Td[i] time for each train. Time will be given in 24H format and colons will be omitted for convenience. For ex.: 9:05AM will be given as "905", or 9:10PM will be given as "2110".

Constrains:

0 < N < 1000

0000 < T[a] < T[d] < 2359

Output Format:

Output integer value of the minimum required platforms.

Sample Input:

3

900 920

910 950

940 1000

Sample Output:

2

Explanation:

We need 2 platforms for #1 and #2 trains. #3 train can use same platform as #1 train, since #1 train will depart by that time

Solution:

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

    int i,n;

    cin>>n;

    int a[n],d[n];

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

        cin>>a[i]>>d[i];

    sort(a,a+n);

    sort(d,d+n);

    int x=1,y=0,p=1,m=1;

    while(x<n&&y<n)

    {

        if(a[x]<d[y])

        {

            p++;

            x++;

            m=max(p,m);

        }

        else

        {

            y++;

            p--;

        }

    }

    cout<<m;

    return 0;

}

Read More

Pattern Printing 3 - CTS2

Write a program to print below pattern. 

Note: Get INPUT using command line

Sample Input and output:

Input:

5

Output:

**********

****  ****

***    ***

**      **

*        *

**      **

***    ***

****  ****

**********

Solution:

#include <stdio.h>

int main(int argc, char *argv[])

{

    int i, j, k;

    int n=atoi(argv[1]);

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n+1-i;j++)

        {

            printf("*");

        }

        for(k=1;k<i;k++)

        {

            printf("  ");

        }

        for(j=1;j<=n+1-i;j++)

        {

            printf("*");

        }

        printf("\n");

    }

    for(i=2;i<=n;i++)

    {

        for(j=1;j<=i;j++)

        {

            printf("*");

        }

        for(k=1;k<=n-i;k++)

        {

            printf("  ");

        }

        for(j=1;j<=i;j++)

        {

            printf("*");

        }

        printf("\n");

    }

    return 0;

}

Read More

Alternative Sorting

Given an array Arr[] of N distinct integers, print the array in such a way that the first element is first maximum and second element is first minimum and so on.

Input:

First line of input contains a single integer T which denotes the number of test cases. Then T test case follows. First line of each test case contains a single integer N which denotes the number of elements in the array. Second line of each test case contains N space separated integers.

Output:

For each test case print the given array in such a way that the first element is first maximum and second element is first minimum and so on.

Constraints:

1<=T<=100

1<=N<=104

1<=Arr[i]<=105

Example:

Input:

2

7

7 1 2 3 4 5 6

8

1 6 9 4 3 7 8 2

Output:

7 1 6 2 5 4 3

9 1 8 2 7 3 6 4

Solution:

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

    int n;

    cin>>n;

    while(n--)

    {

    int k;

    cin>>k;

    int v[k];

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

     cin>>v[i];

    sort(v,v+k);

    int i=0,j=k-1;

    while(i<j)

     cout<<v[j--]<<" "<<v[i++]<<" ";

     if(k%2!=0)

      cout<<v[i];

    cout<<endl;

    }

          return 0;

}

Read More