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

[code lang=”c”]
#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
}
[/code]

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