Given a binary string str[] of size N and an integer M. This binary string can be modified by flipping all the 0’s to 1 which have exactly one 1 as a neighbour. The task is to find the final state of the binary string after M such iterations.
Note: 2?N?103, 1?M?109
Examples:
Input: str=”01100″, M=1
Output: 11110
Explanation: After First Iteration: 11110Input: str = “0110100”, M=3
Output: 1110111
Explanation: After First Iteration: 1110110, After Second Iteration: 1110111, After Third Iteration: Remains the same.
Approach: The solution is based on the observation that the modification can go on for no more than N iterations, because even if in each iteration, atleast one 0 is flipped, then it would go on for maximum N times and, if no zero is flipped in an iteration, then this would mean that the binary string remain in the same state as on the previous step and the simulation is over. Hence, the total number of iterations will be a minimum of N and M. Follow the steps below to solve the problem:
- Initialize the variable N and set its value to the length of the binary string str.
- Set the value of M to the minimum of N or M.
- Iterate in the outer while loop until M is greater than 0.
- Initialize the string s1=”” to store the modified version after the current iteration.
- Iterate in the inner for loop from i=0 to i<N.
- Check the character at the ith index of the given binary string str[].
- If str[i]==’1′, then add this character to the binary string s1.
- Else, check for it’s adjacent characters in the i-1 and i+1 indexes.
- If exactly one 1 is there, then add 1 to the binary string s1.
- Else, add 0 to the binary string s1.
- After the inner loop, check if the binary strings str and s1 are the same or not.
- If yes, then break the outer loop.
- Else, set binary string s1 as the new value of the binary string str and decrease the value of M by 1.
- Finally, print the binary string s1.
Below is the implementation of the above approach.
C++
// C++ program for the above approach.#include <bits/stdc++.h>using namespace std;// Function to find the modified// binary string after M iterationsvoid findString(string str, int M){ int N = str.length(); // Set the value of M to the minimum // of N or M. M = min(M, N); // Declaration of current string state string s1 = ""; // Loop over M iterations while (M != 0) { // Set the current state as null // before each iteration s1 = ""; for (int i = 0; i < N; i++) { if (str[i] == '0') { // Check if this zero has exactly // one 1 as neighbour if ((str[i - 1] == '1' && str[i + 1] != '1') || (str[i - 1] != '1' && str[i + 1] == '1')) // Flip the zero s1 += '1'; else s1 += '0'; } else s1 += '1'; } // If there is no change, // then no need for // further iterations. if (str == s1) break; // Set the current state // as the new previous state str = s1; M--; } cout << s1;}// Driver Codeint main(){ // Given String string str = "0110100"; // Number of Iterations int M = 3; // Function Call findString(str, M); return 0;} |
Java
// Java program for the above approach.import java.io.*;import static java.lang.Math.min;import java.lang.*;class GFG{ // Function to find the modified// binary string after M iterationspublic static void findString(String str, int M){ int N = str.length(); // Set the value of M to the minimum // of N or M. M = Math.min(M, N); // Declaration of current string state String s1 = ""; // Loop over M iterations while (M != 0) { // Set the current state as null // before each iteration s1 = ""; for (int i = 0; i < N; i++) { if (str.charAt(i) == '0') { // Check if this zero has exactly // one 1 as neighbour if ((str.charAt(i) == '1' && str.charAt(i) != '1') || (str.charAt(i) == '1' && str.charAt(i) == '1')) // Flip the zero s1 += '1'; else s1 += '0'; } else s1 += '1'; } // If there is no change, // then no need for // further iterations. if (str == s1) break; // Set the current state // as the new previous state str = s1; M--; } System.out.print(s1);}// Driver Codepublic static void main (String[] args) { // Given String String str = "0110100"; // Number of Iterations int M = 3; // Function Call findString(str, M);}}// This code is contributed by shivanisinghss2110 |
Python3
# Python 3 program for the above approach.# Function to find the modified# binary string after M iterationsdef findString(str,M): N = len(str) # Set the value of M to the minimum # of N or M. M = min(M, N) # Declaration of current string state s1 = "" # Loop over M iterations while (M != 0): # Set the current state as null # before each iteration s1 = "" for i in range(N-1): if (str[i] == '0'): # Check if this zero has exactly # one 1 as neighbour if ((str[i - 1] == '1' and str[i + 1] != '1') or (str[i - 1] != '1' and str[i + 1] == '1')): # Flip the zero s1 += '1' else: s1 += '0' else: s1 += '1' # If there is no change, # then no need for # further iterations. if (str == s1): break s1 += '1' # Set the current state # as the new previous state str = s1 M -= 1 print(s1)# Driver Codeif __name__ == '__main__': # Given String str = "0110100" # Number of Iterations M = 3 # Function Call findString(str, M) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach.using System;class GFG { // Function to find the modified // binary string after M iterations static void findString(string str, int M) { int N = str.Length; // Set the value of M to the minimum // of N or M. M = Math.Min(M, N); // Declaration of current string state string s1 = ""; // Loop over M iterations while (M != 0) { // Set the current state as null // before each iteration s1 = ""; for (int i = 0; i < N; i++) { if (str[i] == '0') { // Check if this zero has exactly // one 1 as neighbour if (((i>0 && str[i - 1] == '1') && (i<N-1 && str[i + 1] != '1')) || ((i>0 && str[i - 1] != '1') && (i<N-1 && str[i + 1] == '1'))) { // Flip the zero s1 += '1'; } else { if(i==0 || i==N-1) { s1 += '1'; } else { s1 += '0'; } } } else { s1 += '1'; } } // If there is no change, // then no need for // further iterations. if (str == s1) break; // Set the current state // as the new previous state //str = s1; M--; } Console.WriteLine(s1); } static void Main() { // Given String string str = "0110100"; // Number of Iterations int M = 3; // Function Call findString(str, M); }}// This code is contributed by divyesh072019. |
Javascript
<script>// Javascript program for the above approach// Function to find the modified// binary let after M iterationsfunction findlet(str, M){ let N = str.length; // Set the value of M to the minimum // of N or M. M = Math.min(M, N); // Declaration of current let state let s1 = ""; // Loop over M iterations while (M != 0) { // Set the current state as null // before each iteration s1 = ""; for (let i = 0; i < N; i++) { if (str[i] == '0') { // Check if this zero has exactly // one 1 as neighbour if ((str[i - 1] == '1' && str[i + 1] != '1') || (str[i - 1] != '1' && str[i + 1] == '1')) // Flip the zero s1 += '1'; else s1 += '0'; } else s1 += '1'; } // If there is no change, // then no need for // further iterations. if (str == s1) break; // Set the current state // as the new previous state str = s1; M--; } document.write(s1);}// Driver Code // Given let let str = "0110100"; // Number of Iterations let M = 3; // Function Call findlet(str, M);// This code is contributed by splevel62.</script> |
Output
1110111
Time Complexity: O(min(M, N)*N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
