Minimizing Binary statements: Transforming a Binary String to all Zeroes
Given a set of N binary statements represented by a string S, where ‘1’ represents a true statement and ‘0’ represents a false one. You can perform the following operation multiple times: choose two indices i and j (1 ≤ i < j ≤ N) such that j – i ≥ 2 and toggle the states of statements i and j, the task is to determine whether it is possible to make all N statements false using these operations. If possible, calculate the minimum number of operations needed to achieve this. If it’s not possible to make all statements false, return -1.
Examples:
Input: N = 6, S = 101101
Output: 2
Explanation: Here, we can perform the operation with ((i, j) = (1, 3) and then with (i, j) = (4, 6) to make all the statements false.Input: N = 4, S = 1111
Output: -1
Explanation: Here, we can’t make all statements false with any operation.
Approach: To solve the problem follow the below observations:
- Case I: In each operation, the count of 1 increases by 0, +2, or -2, so the objective is unachievable if the count of 1 is odd. In all the below cases we consider the count of 1 is even.
- Case II: If there is no 1, then nothing to do.
- Case III: If a count of 1 is greater than or equal to 4, then Let x1, x2,…,xk(k is the count of 1) be the true statements from left to right. Then, one can achieve the objective in k/2 operations by changing the states of statements 1 and xk/2+1, statements 2 and xk/2+2, and so on.
- Case IV: The count of 1 is 2, If the true statements are not adjacent, the answer is 1. Below, assume that they are adjacent, and let X be the statement to the left and Y be the statement to the right.
- If X >=3 , one can achieve the objective in two operations by changing the states of staements 1 and X and then by changing the states of staements 1 and Y.
- If X+1 ≤ N-2, one can again achieve the objective in two operations by changing the states of staements 1 and N and then by changing the states of staements X and Y.
- Case V: Neither of the above is satisfied if X < 3 and X+1>N-2, which happens only if N=3 or 4.
- If N=3, then S is 011 or 110, in which case one can only flip coins 1 and 3, so the objective is unachievable.
- If N=4, X<3, and X+1>N-2, then S is 0110, in which case the objective is achievable in three operations (0110→1111→0101→0000).
Steps to implement the above approach:
- Read the integer ‘n’, the number of statements, and the string ‘s‘, representing the current state of the statements.
- Count the number of ‘1‘s in the string ‘s‘ using the count() function. Let’s call this count ‘one‘.
- Check if the count ‘one‘ is odd:
- If odd, return -1, indicating that it’s not possible to make all statements false.
- Initialize a boolean variable ‘adj’ as false. This will be used to check if adjacent pairs of ‘1’s exist.
- Iterate through the characters of the string ‘s’ from index 0 to ‘n-2’:
- If the current character and the next character are both ‘1’s, set ‘adj’ to true.
- If ‘one’ is not equal to 2 or ‘adj’ is false, calculate the minimum number of operations needed:
- If ‘one’ is greater than or equal to 4, or ‘one’ is 0, or ‘adj’ is false, return ‘one / 2’ as the minimum number of operations.
- If ‘one’ is equal to 2 and ‘adj’ is true, find the position of the leftmost ‘1’ in the string ‘s’. Let’s call this position ‘x’.
- Check for special cases:
- If ‘n’ is 3, return -1 as it’s not possible to achieve the objective.
- If ‘n’ is 4 and ‘s’ is “0110”, return 3 as it can be achieved in 3 operations.
- If none of the special cases apply, check if the position ‘x’ is greater than or equal to 3:
- If yes, return 2 as the objective can be achieved by flipping statements 1 and ‘x’, then statements 1 and the position of the second ‘1’.
- If ‘x+1’ is less than or equal to ‘n-2’:
- If yes, return 2 as the objective can be achieved by flipping statements 1 and ‘n’, then statements ‘x’ and the position of the second ‘1’.
- If none of the above conditions are satisfied, return -1 as the objective cannot be achieved.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to solve the // problem for a single test case int IsPossibleToMakeAllFalse(string s, int n) { // Count the number of //'1's in the string S int one = count(s.begin(), s.end(), '1' ); // If the count 'one' is odd, // it is not possible to make // all statements are false if (one & 1) return -1; // Check if the '1's in the // string S are adjacent or not bool adj = 0; for ( int i = 0; i < n - 1; i++) if (s[i] == '1' and s[i] == s[i + 1]) adj = 1; // If the count 'one' is not 2 // or the '1's are not // adjacent, the objective is // achievable in 'one/2' // operations if (one != 2 or !adj) return one / 2; // If the '1's are adjacent, // find the position of the // leftmost '1' int x = 0; while (s[x] != '1' ) x++; // Check for special cases if (n == 3) return -1; if (n == 4 and s == "0110") return 3; // If 'x' is greater than or // equal to 3, perform two operations: // 1. Flip statements 1 and 'x' // 2. Flip statements 1 and 'y', where // 'y' is the position of the second '1' if (x >= 3) return 2; // If 'x+1' is less than or equal // to 'N-2', perform two operations: // 1. Flip statements 1 and 'N' // 2. Flip statements 'x' and 'y', // where 'y' is the // position of the second '1' if (x + 1 <= n - 2) return 2; // If neither of the above // conditions is satisfied, // return -1 (unachievable) return -1; } // Driver Code int main() { int n = 6; string s = "101101"; // Function Call cout << IsPossibleToMakeAllFalse(s, n) << endl; return 0; } |
Java
import java.util.Scanner; public class Main { // Function to solve the problem for a single test case public static int isPossibleToMakeAllFalse(String s, int n) { // Count the number of '1's in the string s int one = 0 ; for ( char c : s.toCharArray()) { if (c == '1' ) { one++; } } // If the count 'one' is odd, it is not possible to make all statements false if (one % 2 != 0 ) { return - 1 ; } // Check if the '1's in the string s are adjacent or not boolean adj = false ; for ( int i = 0 ; i < n - 1 ; i++) { if (s.charAt(i) == '1' && s.charAt(i) == s.charAt(i + 1 )) { adj = true ; break ; } } // If the count 'one' is not 2 or the '1's are not adjacent, // the objective is achievable in 'one/2' operations if (one != 2 || !adj) { return one / 2 ; } // If the '1's are adjacent, find the position of the leftmost '1' int x = 0 ; while (s.charAt(x) != '1' ) { x++; } // Check for special cases if (n == 3 ) { return - 1 ; } if (n == 4 && s.equals( "0110" )) { return 3 ; } // If 'x' is greater than or equal to 3, perform two operations: // 1. Flip statements 1 and 'x' // 2. Flip statements 1 and 'y', where 'y' is the position of the second '1' if (x >= 3 ) { return 2 ; } // If 'x+1' is less than or equal to 'N-2', perform two operations: // 1. Flip statements 1 and 'N' // 2. Flip statements 'x' and 'y', where 'y' is the position of the second '1' if (x + 1 <= n - 2 ) { return 2 ; } // If neither of the above conditions is satisfied, return -1 (unachievable) return - 1 ; } public static void main(String[] args) { int n = 6 ; String s = "101101" ; // Function Call System.out.println(isPossibleToMakeAllFalse(s, n)); } } |
Python3
# Function to solve the # problem for a single test case def IsPossibleToMakeAllFalse(s, n): # Count the number of #'1's in the string S one = s.count( '1' ) # If the count 'one' is odd, # it is not possible to make # all statements are false if one & 1 : return - 1 # Check if the '1's in the # string S are adjacent or not adj = False for i in range (n - 1 ): if s[i] = = '1' and s[i] = = s[i + 1 ]: adj = True # If the count 'one' is not 2 # or the '1's are not # adjacent, the objective is # achievable in 'one/2' # operations if one ! = 2 or not adj: return one / / 2 # If the '1's are adjacent, # find the position of the # leftmost '1' x = 0 while s[x] ! = '1' : x + = 1 # Check for special cases if n = = 3 : return - 1 if n = = 4 and s = = "0110" : return 3 # If 'x' is greater than or # equal to 3, perform two operations: # 1. Flip statements 1 and 'x' # 2. Flip statements 1 and 'y', where # 'y' is the position of the second '1' if x > = 3 : return 2 # If 'x+1' is less than or equal # to 'N-2', perform two operations: # 1. Flip statements 1 and 'N' # 2. Flip statements 'x' and 'y', # where 'y' is the # position of the second '1' if x + 1 < = n - 2 : return 2 # If neither of the above # conditions is satisfied, # return -1 (unachievable) return - 1 # Driver Code n = 6 s = "101101" # Function Call print (IsPossibleToMakeAllFalse(s, n)) |
C#
using System; class Program { // Function to solve the problem for a vsingle test case static int IsPossibleToMakeAllFalse( string s, int n) { // Count the number of '1's in the string s int one = s.Split( '1' ).Length - 1; // If the count 'one' is odd, it is not possible to make all statements false if (one % 2 != 0) return -1; // Check if the '1's in the string s are adjacent or not bool adj = false ; for ( int i = 0; i < n - 1; i++) { if (s[i] == '1' && s[i] == s[i + 1]) { adj = true ; break ; } } // If the count 'one' is not 2 or the '1's are not adjacent, the objective is achievable in 'one/2' operations if (one != 2 || !adj) return one / 2; // If the '1's are adjacent, find the position of the leftmost '1' int x = 0; while (s[x] != '1' ) { x++; } // Check for special cases if (n == 3) return -1; if (n == 4 && s == "0110" ) return 3; // If 'x' is greater than or equal to 3, perform two operations: // 1. Flip statements 1 and 'x' // 2. Flip statements 1 and 'y', where 'y' is the position of the second '1' if (x >= 3) return 2; // If 'x+1' is less than or equal to 'n-2', perform two operations: // 1. Flip statements 1 and 'n' // 2. Flip statements 'x' and 'y', where 'y' is the position of the second '1' if (x + 1 <= n - 2) return 2; // If neither of the above conditions is satisfied, return -1 (unachievable) return -1; } // Driver Code static void Main() { int n = 6; string s = "101101" ; // Function Call Console.WriteLine(IsPossibleToMakeAllFalse(s, n)); } } //This code is Contributed by chinmaya121221 |
Javascript
function isPossibleToMakeAllFalse(s, n) { // Count the number of '1's in the string s const one = s.split( '1' ).length - 1; // If the count 'one' is odd, it is not possible to make all statements false if (one % 2 !== 0) return -1; // Check if the '1's in the string s are adjacent or not let adj = false ; for (let i = 0; i < n - 1; i++) { if (s[i] === '1' && s[i] === s[i + 1]) { adj = true ; break ; } } // If the count 'one' is not 2 or the '1's are not adjacent, the objective is achievable in 'one/2' operations if (one !== 2 || !adj) return Math.floor(one / 2); // If the '1's are adjacent, find the position of the leftmost '1' let x = 0; while (s[x] !== '1' ) { x++; } // Check for special cases if (n === 3) return -1; if (n === 4 && s === "0110" ) return 3; // If 'x' is greater than or equal to 3, perform two operations: // 1. Flip statements 1 and 'x' // 2. Flip statements 1 and 'y', where 'y' is the position of the second '1' if (x >= 3) return 2; // If 'x+1' is less than or equal to 'n-2', perform two operations: // 1. Flip statements 1 and 'n' // 2. Flip statements 'x' and 'y', where 'y' is the position of the second '1' if (x + 1 <= n - 2) return 2; // If neither of the above conditions is satisfied, return -1 (unachievable) return -1; } // Test case const n = 6; const s = "101101" ; // Function call console.log(isPossibleToMakeAllFalse(s, n)); |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us