Q:

# 11 Pattern Count

This question provides solution to an algorithm problem based on pattern searching came in the coding round of Samsung.

Given a binary string, write an algorithm to find the number of patterns of form 11 where  represents any number of zeroes (minimum requirement is one 0) there should not be any other character except 0 in the  sequence.

Algorithm:

1. Set l = length of string & initialize count to 0.
2. Find the number of 1's in the string. If all entry is 1 then no such pattern exists for the string input.
3. Find first '1' for a 11 pattern
While (String [element]!= '1')
Go to next element.
4. Check if the next element of the string is '0' or not.
5. If the next element is '0'
Continue checking next element until the substring of 0 finishes. ( part in the pattern)
6. Once finished check the next element. If it is '1' increase count.
In the next iteration this '1' element is going to be starting element of next 11 pattern.
7. Continue steps 3 to 6 until string length finishes for processing.
8. Return count.

## C++ implementation for 11 Pattern Count

``````#include <bits/stdc++.h>
using namespace std;

int my(string s){
//set variables
int l=s.length(),count=0;
for(int i=0;i<l;i++){
//count no of 1's
if(s[i]!='0')
count++;
}
//if no of 1=total length then no 11 pattern
if(count==l)
return 0;

int i=0,flag=0,start=0,end=1;
count=0;

while(i<l){
//go to first '1' of a pattern
while(s[i]!='1'){
i++;
}
//first 1 is found,check the next
i=i+1;
//if next is a 0
if(s[i]=='0'){
//procedd till elements are 0
while(s[i]=='0')
i++;
//if the element after end of 0 substring is 1
if(s[i]=='1'){
//pattern is found & increase count
count++;
}
}
}
return count; //return no of pattern
}

int main()
{

cout<<"program to find no of 11 patterns in string"<<endl;
string s;
cout<<"enter string"<<endl;
cin>>s;
int k=my(s);
cout<<k<<endl;

return 0;
}
``````

Output

```First run:
program to find no of 11 patterns in string
enter string
001010100001101
4

Second run:
program to find no of 11 patterns in string
enter string
111111111111111111111110
0```