Q:

Given a binary string, write an algorithm 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 the [0] sequence

0

1[0]1 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 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 the [0] sequence.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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 1[0]1 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. ([0] 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 1[0]1 pattern.
  7. Continue steps 3 to 6 until string length finishes for processing.
  8. Return count.
 

C++ implementation for 1[0]1 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 1[0]1 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 1[0]1 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 1[0]1 patterns in string 
enter string 
001010100001101
4

Second run:
program to find no of 1[0]1 patterns in string 
enter string 
111111111111111111111110 
0

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now