by Given a binary string contains 0’s and 1’s. Write a program to find the longest contiguous occurrence of 0’s and 1’s.
For example:
Input string — 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1
Length_0: 3 Length_1: 3
Input string — 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0
Length_0: 5 Length_1: 3
Algorithm
- Define max_0_length, max_1_length, length_0, length_1 and prev.
- Iterate through array.
- If value encountered is 0
- If prev is same as current, then length_0 ++. Check whether length_0 > max_length and set max_length = length_0 if true.
- If prev is not same as current, then length_0 = 1 and length_1 = 0.
- If value encountered is 1
- If prev is same as current, then length_1++. Check whether length_1 > max_length and set max_length = length_1 if true.
- If prev is not same as current, then length_1 = 1 and length_0 = 0.
- If value encountered is 0
- Iterate through array.
Implementation
Let’s have a look into the sample program to solve the above problem.
#include <iostream>
using namespace std;
#define MAX_ARRAY_ITEM 20
void check_length (int* arr, int size)
{
int max_0_length = 0;
int max_1_length = 0;
int length_0 = 0;
int length_1 = 0;
int prev = -1;
for (int i = 0; i < size; i++) {
switch (arr[i]) {
case 0:
if (prev == arr[i]) {
length_0++;
if (max_0_length < length_0) {
max_0_length = length_0;
}
} else {
length_0 = 1;
length_1 = 0;
prev = 0;
}
break;
case 1:
if (prev == arr[i]) {
length_1++;
if (max_1_length < length_1) {
max_1_length = length_1;
}
} else {
length_1 = 1;
length_0 = 0;
prev = 1;
}
break;
}
}
cout << "Length_0: " << max_0_length << " Length_1: " << max_1_length << endl;
}
int main ()
{
int arr[MAX_ARRAY_ITEM];
srand (26);
for (int i = 0; i < MAX_ARRAY_ITEM; i++) {
arr[i] = rand() & 0x1;
}
for (int i = 0; i < MAX_ARRAY_ITEM; i++) {
cout << arr[i] << " " ;
}
cout << "\n";
check_length (arr, MAX_ARRAY_ITEM);
}
Let’s look into the output of the above program.
1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0
Length_0: 5 Length_1: 3
