Concepts Used

Strings

Difficulty Level

Easy

Problem Statement (Simplified):

For a given string S and number of rows R, we have to arrange each character on rows in a vertical zigzag format, and then print values row-wise.

See original problem statement here

Can you guess the Time Complexity of this solution?

Test Case

Input:
1
9 3
prepbytes

Output:
pbsrpyeet

Example:
For string 'prepbytes' and '3' rows, we arrange it in the following pattern.

p.......b.......s
..r...p...y...e..
....e.......t....

Now we print this row-wise, so the answer will be 'pbsrpyeet'.

Solving Approach :

> 1) To make a zigzag print, we print each character on the next row, and when row ends it goes back to 1st row. Refer some online programming courses to repeat this pattern until the string ends.
> 2) As we can see pattern repeats once it reaches back to 1st row, So we divide the string into different parts and make a set of substrings for each repetition, each substring containing 2 x ( R - 1) characters. For the above example, the above string converts into 3 substrings that are prep, byte, and s.
> 3) Now we can see 1st row contains 1st element of each substring, and the last row contains a mid element of each substring.
> 4) For the rest of the elements, we notice every ith
row contains ith and ith element in serial pattern.
> 5) Now we know all the patterns, we print them in serial order from every substring keeping notice that the current element does not go beyond the size of the string.

Example

  • Lets assume string S to be 'expertcoderprogram' and number of rows R be 4.
  • We can arrange this in this pattern :
e . . . . . . c . . . . . r . . . . .  
. x . . . . t . o . . . p . o . . . m  
. . p . . r . . . d . r . . . g . a .  
. . . e . . . . . . e . . . . . r . .  
  • We can see in each repition pattern there are i.e. characters. Hence there are 6 characters in each repetition pattern.
  • As length of string S is 18, so there will be total 3 repetion patterns containing 6 elements each.
  • These repetions strings are 'expert', 'coderp' and 'rogram'.
  • Let length of each repetition string be N.
  • For every row we print:

> For 1st row: We print 1st element of each repetition string.
> See Graphic-1 Above
>
> Hence we print ecr.

> For 2nd row: We print 2nd and (N-2+2)th` i.e. 3rd element of each repetition string.
> See Graphic-2 Above
>
> Hence we print xtopom.

> For 3rd row: We print 3rd and (N-3+2)th i.e. 5th element of each repetition string.
> See Graphic-3 Above
>
> Hence we print prdrga.

> For 4th row: We print 4th element of each repetition string.
> See Graphic-4 Above
>
> Hence we print eer.

Solutions

 #include <stdio.h>

    int main()
    {
      int test;
      scanf("%d", &test);

      while(test--){

        char a[1001], b[1001];
        scanf("%s%s", a,b);

        int found = 0;

        if(strlen(a)>=strlen(b)){

            for(int i=0; i<=strlen(a)-strlen(b) && !found; i++){

              found = 1;

              for(int j = 0; j<strlen(b); j++){

                  if( a[i+j] != b[j] ){
                      found = 0;
                      break;
                  }

                }
            }
        }

        if(found == 1)
            printf("YES\n");
        else
            printf("NO\n");


      }

      return 0;
    }
#include <bits/stdc++.h>
    using namespace std;

    int main()
    {
      int test;
      cin>>test;

      while(test--){

          int N, R;
          cin>>N>>R;

          char a[N];
          cin>>a;

          int pairSize = 2*(R - 1);
          if(pairSize == 0)
            pairSize=1;
          for(int i=0; i<=pairSize/2; i++){

            for(int j=0; j<(N/pairSize)+1; j++){

              int pos = i+(pairSize*j);
              int revPos = (pairSize - i) + pairSize*j; 
              if( ((pos%pairSize)==0 || (pos+(pairSize/2))%pairSize == 0 ) && pos < N)
                  cout<<a[(i + pairSize*j)];
              else{
                  if( pos < N )
                    cout<<a[pos];
                  if( revPos < N )
                    cout<<a[revPos];
              }

            }

          }

          cout<<endl;

      }

      return 0;
    }



import java.util.*;
    import java.io.*;
    import java.lang.Math;

    public class Main {
      public static void main(String args[]) throws IOException {

        Scanner sc= new Scanner(System.in);
        int test = sc.nextInt();
          while(test != 0){

            int N = sc.nextInt();
            int R = sc.nextInt();

            String a = sc.next();

            int pairSize = 2*(R - 1);
            if(pairSize == 0)
              pairSize=1;
            for(int i=0; i<=pairSize/2; i++){

              for(int j=0; j<(N/pairSize)+1; j++){

                int pos = i+(pairSize*j);
                int revPos = (pairSize - i) + pairSize*j; 
                if( ((pos%pairSize)==0 || (pos+(pairSize/2))%pairSize == 0 ) && pos < N)
                    System.out.print(a.charAt(i + pairSize*j));
                else{
                    if( pos < N )
                      System.out.print(a.charAt(pos));
                    if( revPos < N )
                      System.out.print(a.charAt(revPos));
                }

              }

            }

            System.out.println();

            test--;
          }

      }
    }


Space Complexity

O(1)

Previous post Missing in AP
Next post Fair Distribution of Chocolates

Leave a Reply

Your email address will not be published. Required fields are marked *