The simplified problem statement is as follows.
Given a sequence of 0 and 1s. Check if contains a continuous sequence of 0/1 of length 7.
For example see some input output combinations
Input Output
——————————————
10001010010011 NO
1000000001100 YES
000111111111110 YES
Your program should accept a sequence of 0, 1s as input and print YES of there is a sequence of 7 0/1s in it or NO if does not contain such a sequence.
The algorithm is as follows.
We maintain a state variable to see if we are getting a sequence 0s or sequence of 1s. We also use a continuity counter to track the maximum number of similar symbols. If this counter reaches 7 anytime we break and declare the result as YES.
If we finish processing the input without the counter reaching 7 anytime, we output the result as NO.
Here is the C++ implementation of the above algorithm.
#include <iostream> | |
using namespace std; | |
bool containsSequence(string input) | |
{ | |
if( input.size() < 7 ) | |
{ | |
return false; | |
} | |
else | |
{ | |
int i; | |
bool dangerous = false; | |
int ccount = 0; | |
int state = -1; //initial state | |
for( i = 0; i < input.size(); i++ ) | |
{ | |
if( input[i] == '0' ) | |
{ | |
if( state != 0 ) //sequence broken | |
{ | |
ccount = 1; //reset count | |
state = 0; //change the state | |
} | |
else //sequence continues | |
ccount++; | |
} | |
else | |
{ | |
if( state != 1 )//sequence broken | |
{ | |
ccount = 1; | |
state = 1; | |
} | |
else | |
ccount++; | |
} | |
if( ccount == 7 ) //sequence found | |
{ | |
return true; | |
} | |
} | |
return false; | |
} | |
} | |
int main() { | |
string input; | |
cin >> input; | |
if( containsSequence(input) ) | |
cout << "YES" << endl; | |
else | |
cout << "NO" << endl; | |
return 0; | |
} |