hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Binary strings with no consecutive 1s
Problem: Binary strings with no consecutive 1s.
Problem Link: https://www.codingninjas.com/codestudio/problems/binary-strings-with-no-consecutive-1s_893001
Companies Asked: PayTM
Approach:
For each of the K positions in a string, I tried to place both '1' and '0'.
If the last character is set as '1' then, I surely set the current character '0'.
If the last character is set as '0' then, I set both '0' and '1' as the current character.
And then call the recursive function to set the next characters until the length reached K.
Once the length becomes K, add them to the resultant array.
Return the resultant array.
Time and Space Complexity:
Time Complexity: O(2^(K+1))
Space Complexity: O(K*2^K)
Code [C++]
string makestring(int mask, int k){
string str = "";
for(int i=0; i<k; i++){
bool bit = (mask >> i) & 1;
str += (!bit ? '0' : '1');
}
return str;
}
void recurse(int pos, int mask, int k, bool last, vector<string> & ans){
if(pos == k){
ans.push_back(makestring(mask, k));
return;
}
if(!last){
recurse(pos+1, (mask & ~(1<<pos)), k, 0, ans);
recurse(pos+1, (mask | (1<<pos)), k, 1, ans);
}
else{
recurse(pos+1, (mask & ~(1<<pos)), k, 0, ans);
}
}
vector<string> generateString(int k) {
vector<string>ans;
if(k){
recurse(1, 0, k, 0, ans);
recurse(1, 1, k, 1, ans);
}
return ans;
}