1[0]1 Pattern Count | Samsung

Question

Write a program to find the 1[0]1 pattern count. Given a string, your task is to find the number of patterns of form 1[0]1 where [0] represents any number of zeroes(minimum requirement is one 0) there should not be any other character except  0 in [0] sequence.

Logic

• The logic is simple. When we encounter a character other than 1, we continue traversing the string.
• If 1 is encountered then check whether zeros are coming after that. We use Zcnt variable to count the number of zero.
• When we encounter 1 after repeating zeros, check whether the Zcnt is positive. If so then increment the count of 1[0]1 pattern count.
• Repeat the same procedure till we reach the end of the string.

Program

#include<stdio.h>
#include<string.h>
int main()
{
    char s[50];
    int i,j,t,n,Zcnt=0,count=0;
    printf("enter the string");
    scanf("%s",&s);
    n=strlen(s);
    /*ascii of
      0 ->48
      1-> 49 */
    for(i=0;i<n;i++)
    {
        t=s[i];                 //Storing ascii of character
        if(t==48 || t>57)
            continue;           //continue if '0' or not a number
        else
        {
            if(t==49)           //character is '1'
            {
                j=i+1;          //move one position forward
                t=s[j];
                while(t==48)    //character is '0'
                {
                    Zcnt++;     //increment ZeroCount
                    j++;
                    t=s[j];
                }
                /*character is 1 and Zcnt is greater than zero*/
                if(t==49&&Zcnt>0)
                  {
                     count++;   //count of 1[0]1 pattern
                     Zcnt=0;    //reset ZeroCount
                  }
            }
        }
        i=j;                    //reset i
    }
    printf("%d",count);         //total 1[0]1 patterns
}

Analysis

Time complexity – O(n) since we are traversing the whole string.

Space complexity- O(1) since we are not using any storage relative to the input.

You might also like…

Triplet Sum in Array | Amazon | Samsung