Home » Interview coding problems/challenges

1[0]1 Pattern Count

1[0]1 Pattern Count: Here, we are going to solve an algorithm problem based on pattern searching came in the coding round of Samsung. Submitted by Radib Kar, on November 26, 2018

Description:

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

Problem statement

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.

Solution

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