Introduction
Starting with the most intuitive brute force solution is the best way to approach a problem. After you've solved it, see if you can improve it in any way. Optimization techniques depend on the nature of the problem and its data structures. Sorting, for example, can often improve the complexity of array and string problems.
These optimization strategies are the result of a lot of trial and error. Try to think about why you've done it and what you've done to find the patterns in question.
Today we'll look at an array problem that appears to be about bits. So, let the party begin.
You can also check, Difference Between Analog and Digital Computer
Problem Statement - Bit Stuffing
You are given an array ‘ARR’ of 0s and 1s. You have to insert a zero in the array such that there are no more than five consecutive 1s in the array.
Example
Approach
Let's have a look at what bit stuffing implies. If we have an array of 0s and 1s, we must check if there are any series of 1s whose length is longer than 5, and if so, we must insert a 0 to ensure that there is no series of 1s whose length is longer than 5.
The simplest solution is to loop through the array and count the number of ones, then insert a 0 between them if the count is greater than 5.
Now that we’ve discussed the approach, let’s see how the algorithm works.
- Initialize a variable 'i', 'COUNT', and an array ‘ANS’ to store the current index, the count of consecutive 1s, and the answer array respectively.
- Next, loop through the array and if the current element is 1, we will increment ‘i’ until ‘i < ARR.size() and ARR[i] == 1 && COUNT <= 5’ to get the length of series of 1s, and insert the elements in the ‘ANS’ as well..
- If the length of the current series is greater than 5, we insert a 0 in the ‘ANS’ array if the current element is not zero. Otherwise, insert ARR[i].
- Next, increment index, ‘i’ and update ‘COUNT’ to zero.
Let’s try to code this solution now.
Program
#include <iostream>
#include <vector>
using namespace std;
// Function for Bit Stuffing.
vector<int> bitStuffing(vector<int> &arr)
{
// Initialize 'i' with zero to store the current index.
int i = 0;
// Initialize 'COUNT' with zero to store the count of consecutive 1s.
int count = 0;
// Declare a vector, 'ANS' to store the array after bit stuffing.
vector<int> ans;
// Loop through the array.
while (i < arr.size())
{
// Count the number of consecutive 1s.
while (i < arr.size() && arr[i] == 1 && count < 5)
{
ans.emplace_back(arr[i]);
i++;
count++;
}
// If the count of consecutive 1s is greater than five. Skip if the next element is zero, otherwise push a zero..
if (arr[i] == 0)
{
ans.emplace_back(arr[i]);
i++;
} else if (count == 5)
{
ans.emplace_back(0);
}
count = 0;
}
return ans;
}
// Main.
int main()
{
int n;
cout << "Enter the size of the array: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements in the array: ";
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "Before Bit Stuffing: ";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
arr = bitStuffing(arr);
cout << "After Bit Stuffing: ";
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Input
Enter the size of the array: 12
Enter the elements in the array: 0 1 1 0 1 1 1 1 1 1 1 0Output
Before Bit Stuffing: 0 1 1 0 1 1 1 1 1 1 1 0
After Bit Stuffing: 0 1 1 0 1 1 1 1 1 0 1 1 0Complexity Analysis
Time Complexity
O(N), where ‘N’ is the size of the array ‘ARR’.
Since we traverse the array once, the time complexity is O(N).
Space Complexity
O(N), where ‘N’ is the size of the array ‘ARR’.
As we are only initializing vector ‘ANS’ of size ‘N’. Hence the space complexity is O(N).
Also see, Euclid GCD Algorithm
84+ registered 