Minimum flips to make all 1s in left and 0s in right | Set 2
Given a binary string, we can flip any bit in the given string i.e., convert 1 to 0 or vice-versa. Calculate the minimum flips required to make all 1s on the left and all 0s on the right.
Examples :
Input: 1011000
Output: 1
Explanation: 1 flip is required to make it 1111000.Input: 00001
Output: 2
Explanation: 2 flips required to make it 10000.
We have discussed a bitmask based solution in below post. Minimum flips to make all 1s in left and 0s in right | Set 1 (Using Bitmask)
It can be done with O(N) time complexity (where N – number of bits) and O(N) extra memory
- Calculate number of flips of ‘0’ needed to be done while moving from left to right to have all ‘1’ in bits.
- Calculate number of flips of ‘1’ needed to be done while moving from right to left to have all ‘0’ in bits.
- Traversing through all positions between bits and find minimal sum of ‘0’-flips+’1′-flips from both arrays.
Implementation:
C++
// CPP program to find minimum flips required // to make all 1s in left and 0s in right. #include <bits/stdc++.h> using namespace std; int minimalFilps(string bits) { int n = bits.length(); // two arrays will keep the count for number // of 0s' and 1s' to be flipped while // traversing from left to right and right to // left respectively int flipsFromLeft[n]; int flipsFromRight[n]; // Fill flipsFromLeft[] int flips = 0; for ( int i = 0; i < n; i++) { if (bits[i] == '0' ) flips++; flipsFromLeft[i] = flips; } // Fill flipsFromRight[] flips = 0; for ( int i = n - 1; i >= 0; i--) { if (bits[i] == '1' ) flips++; flipsFromRight[i] = flips; } // initialize minFlip to highest int value. If sum // of leftflip and rightFlip is smaller than minflips, // then update minFlips int minFlips = INT_MAX; for ( int i = 1; i < n; i++) { if (flipsFromLeft[i - 1] + flipsFromRight[i] < minFlips) minFlips = flipsFromLeft[i - 1] + flipsFromRight[i]; } return minFlips; } // Driver code int main() { string bits = "00001" ; cout << minimalFilps(bits) << endl; return 0; } |
Java
// Java program to find minimum flips required // to make all 1s in left and 0s in right. import java.io.*; class GFG { static int minimalFilps(String bits) { int n = bits.length(); // two arrays will keep the count // for number of 0s' and 1s' to be // flipped while traversing from // left to right and right to // left respectively int flipsFromLeft[] = new int [n]; int flipsFromRight[] = new int [n] ; // Fill flipsFromLeft[] int flips = 0 ; for ( int i = 0 ; i < n; i++) { if (bits.charAt(i) == '0' ) flips++; flipsFromLeft[i] = flips; } // Fill flipsFromRight[] flips = 0 ; for ( int i = n - 1 ; i >= 0 ; i--) { if (bits.charAt(i) == '1' ) flips++; flipsFromRight[i] = flips; } // initialize minFlip to highest int value. If sum // of leftflip and rightFlip is smaller than minflips, // then update minFlips int minFlips = Integer.MAX_VALUE; for ( int i = 1 ; i < n; i++) { if (flipsFromLeft[i - 1 ] + flipsFromRight[i] < minFlips) minFlips = flipsFromLeft[i - 1 ] + flipsFromRight[i]; } return minFlips; } // Driver code public static void main (String[] args) { String bits = "00001" ; System.out.println(minimalFilps(bits)); } } // This code is contributed by vt_m. |
Python3
# Python 3 program to find minimum flips required # to make all 1s in left and 0s in right. import sys def minimalFilps(bits): n = len (bits) # two arrays will keep the count for number # of 0s' and 1s' to be flipped while # traversing from left to right and right to # left respectively flipsFromLeft = [ 0 for i in range (n)] flipsFromRight = [ 0 for i in range (n)] # Fill flipsFromLeft[] flips = 0 for i in range ( 0 , n, 1 ): if (bits[i] = = '0' ): flips = flips + 1 flipsFromLeft[i] = flips # Fill flipsFromRight[] flips = 0 i = n - 1 while (i > = 0 ): if (bits[i] = = '1' ): flips = flips + 1 i = i - 1 flipsFromRight[i] = flips # initialize minFlip to highest int value. # If sum of leftflip and rightFlip is smaller # than minflips, then update minFlips minFlips = sys.maxsize for i in range ( 1 , n, 1 ): if (flipsFromLeft[i - 1 ] + flipsFromRight[i] < minFlips): minFlips = (flipsFromLeft[i - 1 ] + flipsFromRight[i]) return minFlips # Driver code if __name__ = = '__main__' : bits = "00001" print (minimalFilps(bits)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to find minimum flips required // to make all 1s in left and 0s in right. using System; class GFG { static int minimalFilps(String bits) { int n = bits.Length; // two arrays will keep the count // for number of 0s' and 1s' to be // flipped while traversing from // left to right and right to // left respectively int []flipsFromLeft = new int [n]; int []flipsFromRight = new int [n] ; // Fill flipsFromLeft[] int flips = 0; for ( int i = 0; i < n; i++) { if (bits[i] == '0' ) flips++; flipsFromLeft[i] = flips; } // Fill flipsFromRight[] flips = 0; for ( int i = n - 1; i >= 0; i--) { if (bits[i] == '1' ) flips++; flipsFromRight[i] = flips; } // initialize minFlip to highest int value. // If sum of leftflip and rightFlip is smaller // than minflips, then update minFlips int minFlips = int .MaxValue; for ( int i = 1; i < n; i++) { if (flipsFromLeft[i - 1] + flipsFromRight[i] < minFlips) minFlips = flipsFromLeft[i - 1] + flipsFromRight[i]; } return minFlips; } // Driver code public static void Main () { string bits = "00001" ; Console.WriteLine(minimalFilps(bits)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find minimum // flips required to make all // 1s in left and 0s in right. function minimalFilps( $bits ) { $n = strlen ( $bits ); // two arrays will keep the // count for number of 0s' // and 1s' to be flipped // while traversing from // left to right and right // to left respectively $flipsFromLeft [ $n ] = 0; $flipsFromRight [ $n ] = 0; // Fill flipsFromLeft[] $flips = 0; for ( $i = 0; $i < $n ; $i ++) { if ( $bits [ $i ] == '0' ) $flips ++; $flipsFromLeft [ $i ] = $flips ; } // Fill flipsFromRight[] $flips = 0; for ( $i = $n - 1; $i >= 0; $i --) { if ( $bits [ $i ] == '1' ) $flips ++; $flipsFromRight [ $i ] = $flips ; } // initialize minFlip to // highest int value. If sum // of leftflip and rightFlip // is smaller than minflips, // then update minFlips $INT_MAX =2147483647; $minFlips = $INT_MAX ; for ( $i = 1; $i < $n ; $i ++) { if ( $flipsFromLeft [ $i - 1] + $flipsFromRight [ $i ] < $minFlips ) $minFlips = $flipsFromLeft [ $i - 1] + $flipsFromRight [ $i ]; } return $minFlips ; } // Driver Code $bits = "00001" ; echo minimalFilps( $bits ) ; // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript program to find minimum flips required // to make all 1s in left and 0s in right. function minimalFilps(bits) { let n = bits.length; // two arrays will keep the count // for number of 0s' and 1s' to be // flipped while traversing from // left to right and right to // left respectively let flipsFromLeft = new Array(n); flipsFromLeft.fill(0); let flipsFromRight = new Array(n); flipsFromRight.fill(0); // Fill flipsFromLeft[] let flips = 0; for (let i = 0; i < n; i++) { if (bits[i] == '0' ) flips++; flipsFromLeft[i] = flips; } // Fill flipsFromRight[] flips = 0; for (let i = n - 1; i >= 0; i--) { if (bits[i] == '1' ) flips++; flipsFromRight[i] = flips; } // initialize minFlip to highest int value. // If sum of leftflip and rightFlip is smaller // than minflips, then update minFlips let minFlips = Number.MAX_VALUE; for (let i = 1; i < n; i++) { if (flipsFromLeft[i - 1] + flipsFromRight[i] < minFlips) minFlips = flipsFromLeft[i - 1] + flipsFromRight[i]; } return minFlips; } let bits = "00001" ; document.write(minimalFilps(bits)); // This code is contributed by divyesh072019. </script> |
Output
2
Time complexity: O(N) where N is the length of the given binary string.
Auxiliary space: O(N), for creating arrays flipsFromLeft and flipsFromRight of size N.