Converts the given binary string to another binary string, with minimum operands flipping all bits except one

In this problem, we need to convert one binary string to another binary string by flipping the characters of the string. We can save any set bits and flip other bits, and we need to calculate the total operations to implement another string by doing this.

We can solve the problem based on the total number of "01" and "10" pairs in the given string.

Problem Statement- We are given two strings of the same length, named str1 and str2, containing "0" and "1" characters, representing binary strings. We need to convert the string str1 to str2 by doing the following.

• We can select any set bit and flip all other bits. Flip bits means converting "0" to "1" and "1" to "0".

• If str1 cannot be converted to str2, print -1.

Example

enter

str1 = "001001111", str2 = "011111000";

Output

3

Explanation−

• In the first operation, we keep the "1" of the second index unchanged and flip all other characters in str1. Therefore, str1 will be 111110000.

• In the second operation, we keep the "1" at index 0 unchanged and flip all other characters. Therefore, str1 will be 100001111.

• In the last operation, we save "1" at the 5th index. Therefore, str1 will become 011111000.

enter

 str1 = "0000", str2 = "1111";

Output

-1

Explanation - Cannot convert str1 to str2 because str1 does not contain any "1" character to save.

enter

 str1 = "0111", str2 = "1000";

Output

-1

Description - Unable to convert str1 to str2.

method 1

We can solve problems through observation. The observation is that when we hold any single set bit and perform 2 operations we can get the same string. Therefore, we need to choose a different 1 index to make changes to the string.

Also, we need to perform 2 operations to convert the 01 pair to 10. For example, leave "1" in "01". So, we get "11". After that, keep "1" at the 0th index in "11" so we get "10".

To get the answer, 01 (0 -> str1, 1 -> str2) and 10 (1 -> str1, 0 -> str2) should be the same. Otherwise, we can say that the answer does not exist.

Our main goal is to minimize the "01" and "10" pairs, since we can convert "01" to "10" in 2 operations.

algorithm

Step 1- Define the totalOperatrions() function to calculate the number of operations required to convert str1 to str2.

Step 1.2 - Initialize the count10 and count01 variables to store the "01" and "10" pairs in a string.

Step 1.3 - Loop through the strings and count pairs of 01 and 10 in both strings.

Step 1.4− If count10 and count01 are the same, return 2*count10. Otherwise, -1 is returned.

Step 2- Define the minimumOperations() function to calculate the minimum operations required to convert str1 to str2.

Step 3 - Initialize "ans" with the maximum value.

Step 4 - Call the totalOperations() function using the original string and store the result in the "operation1" variable. If the return value is not equal to -1, the minimum value from ans and operation 1 is stored in ans.

Step 5- Now we will modify the string to minimize the 01 and 10 pairs. Therefore, define stringModification() function.

Step 5.1 - In the function, we find the first pair of "1ch" in the string and pass "ch" as parameter, which can be "0" or "1". So the pair should look like 1 -> str1 and ch -> str.

Step 5.2- If the "1ch" pair is not found, return false.

Step 5.3 − If a "1ch" pair is found, keep the pair unchanged and flip the other characters of str1.

Step 6 - Execute the stringModification function to keep the "11" pair unchanged and flip the other characters. After that, the totalOperations() function is called again to find the operations required to convert str1 to str2.

Step 7− If operation 2 is not equal to -1, store the minimum value in "ans" or "1 operation 2" in "ans". Here, we added 1 because we modified the string using one operation.

Step 8 - Modify the string by leaving the first "10" pair unchanged, and calculate the operands. Again assign the minimum value to "ans".

Step 9− If "ans" is equal to INT_MAX, return −1. Otherwise, return ans.

Example

#include <bits/stdc++.h>
using namespace std;

// counting 01 and 10 pairs
int totalOperations(string str1, string str2) {
    int len = str1.size();
    int count10 = 0, count01 = 0;
    for (int p = 0; p < len; p++) {
        // If characters at p index are not same
        if (str1[p] != str2[p]) {
            // Increase count01 if 0(str1)-1(str2), else count10 if 1(str1)-0(str2)
            if (str1[p] == '0')
                count01++;
            else
                count10++;
        }
    }
    // If we have euqal number of 01 and 10 pairs, we need 2 operations to flip one pair.
    if (count01 == count10)
        return 2 * count01;
    return -1;
}
bool StringModification(string &temp1, string &temp2, char ch) {
    int len = temp1.size();
    int index = -1;
    // Find the pair of 1c character. (1 -> temp1, c -> temp2)
    for (int p = 0; p < len; p++) {
        if (temp1[p] == '1' && temp2[p] == ch) {
            index = p;
            break;
        }
    }
    // return 0 if pair is not found
    if (index == -1)
        return false;
    // Flip other characters in both strings
    for (int p = 0; p < len; p++) {
        if (p != index) {
            if (temp1[p] == '1')
                temp1[p] = '0';
            else
                temp1[p] = '1';
        }
    }
    return true;
}
// finding minimum operations
int minimumOperations(string str1, string str2) {
    int ans = INT_MAX;
    // first case with initial strings
    int operation1 = totalOperations(str1, str2);
    if (operation1 != -1)
        ans = min(ans, operation1);
    string temp1 = str1, temp2 = str2;
    // Case 2, modification for 11 pair
    if (StringModification(temp1, temp2, '1')) {
        // get operations after modification
        int operation2 = totalOperations(temp1, temp2);
        // adding 1 to operation2 as we have done one modification initially
        if (operation2 != -1)
            ans = min(ans, 1 + operation2);
    }
    // Case 3 modification for 10 pair
    temp1 = str1, temp2 = str2;
    if (StringModification(temp1, temp2, '0')) {
        int operation3 = totalOperations(temp1, temp2);
        if (operation3 != -1)
            ans = min(ans, 1 + operation3);
    }
    if (ans == INT_MAX)
        return -1;
    else
        return ans;
}
int main() {
    string str1 = "001001111";
    string str2 = "011111000";
    int ans = minimumOperations(str1, str2);
    if (ans == -1){
        cout << "S1 to S2 conversion is not possible";
    }
    else{
        cout << "Minimum number of operations required are: " << ans << "\n";
    }
    return 0;
}

Output

Minimum number of operations required are: 3

Time complexity− O(N), because we iterate over the string in stringModification() and totalOperations() functions.

Space Complexity− O(1), since we modify the same string without using any extra space.

In the code, our main purpose is to reduce the number of 01 and 10 pairs in a given string after modifying the string to minimize operations. Programmers can use various inputs and try to understand the answers.

The above is the detailed content of Converts the given binary string to another binary string, with minimum operands flipping all bits except one. For more information, please follow other related articles on the PHP Chinese website!