×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.