Given binary string str. In a single operation, we can change any ‘1’ to ‘0’ or any ‘0’ to ‘1’. The task is to make minimum number of changes in the string such that if we take any prefix of the string, the number of 1’s should be greater than or equal number of 0’s.
Examples:
Input: str = “10001”
Output: 1
We can change str[2] from ‘0’ to ‘1’.
Input: str = “0000”
Output: 2
Approach: The problem can be solved greedily. The first character of the string has to be 1. Then for the rest of the string, we traverse through the string character by character and check if the required condition is fulfilled or not, if not then we increase the count of changes required.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum// changes requiredint minChanges(string str, int n){ // To store the count of minimum changes, // number of ones and the number of zeroes int count = 0, zeros = 0, ones = 0; // First character has to be '1' if (str[0] != '1') { count++; ones++; } for (int i = 1; i < n; i++) { if (str[i] == '0') zeros++; else ones++; // If condition fails // changes need to be made if (zeros > ones) { zeros--; ones++; count++; } } // Return the required count return count;}// Driver codeint main(){ string str = "0000"; int n = str.length(); cout << minChanges(str, n); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to return the minimum // changes required static int minChanges(char[] str, int n) { // To store the count of minimum changes, // number of ones and the number of zeroes int count = 0, zeros = 0, ones = 0; // First character has to be '1' if (str[0] != '1') { count++; ones++; } for (int i = 1; i < n; i++) { if (str[i] == '0') zeros++; else ones++; // If condition fails // changes need to be made if (zeros > ones) { zeros--; ones++; count++; } } // Return the required count return count; } // Driver code public static void main(String[] args){ char []str = "0000".toCharArray(); int n = str.length; System.out.print(minChanges(str, n)); }}// This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function to return the minimum# changes requireddef minChanges(str, n): # To store the count of minimum changes, # number of ones and the number of zeroes count, zeros, ones = 0, 0, 0 # First character has to be '1' if (ord(str[0])!= ord('1')): count += 1 ones += 1 for i in range(1, n): if (ord(str[i]) == ord('0')): zeros += 1 else: ones += 1 # If condition fails # changes need to be made if (zeros > ones): zeros -= 1 ones += 1 count += 1 # Return the required count return count# Driver codeif __name__ == '__main__': str = "0000" n = len(str) print(minChanges(str, n))# This code contributed by PrinciRaj1992 |
C#
// C# implementation of the approachusing System;class GFG {// Function to return the minimum // changes required static int minChanges(char[] str, int n) { // To store the count of minimum changes, // number of ones and the number of zeroes int count = 0, zeros = 0, ones = 0; // First character has to be '1' if (str[0] != '1') { count++; ones++; } for (int i = 1; i < n; i++) { if (str[i] == '0') zeros++; else ones++; // If condition fails // changes need to be made if (zeros > ones) { zeros--; ones++; count++; } } // Return the required count return count; } // Driver code public static void Main(String[] args){ char []str = "0000".ToCharArray(); int n = str.Length; Console.Write(minChanges(str, n)); }}// This code contributed by Rajput-Ji |
PHP
<?php// PHP implementation of the approach// Function to return the minimum// changes requiredfunction minChanges($str, $n){ // To store the count of minimum changes, // number of ones and the number of zeroes $count = $zeros = $ones = 0; // First character has to be '1' if ($str[0] != '1') { $count++; $ones++; } for ($i = 1; $i < $n; $i++) { if ($str[$i] == '0') $zeros++; else $ones++; // If condition fails // changes need to be made if ($zeros > $ones) { $zeros--; $ones++; $count++; } } // Return the required count return $count;}// Driver code$str = "0000";$n = strlen($str);echo minChanges($str, $n);// This code is contributed by mits?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the minimum // changes required function minChanges(str, n) { // To store the count of minimum changes, // number of ones and the number of zeroes let count = 0, zeros = 0, ones = 0; // First character has to be '1' if (str[0] != '1') { count++; ones++; } for (let i = 1; i < n; i++) { if (str[i] == '0') zeros++; else ones++; // If condition fails // changes need to be made if (zeros > ones) { zeros--; ones++; count++; } } // Return the required count return count; } // Driver Code let str = "0000".split(''); let n = str.length; document.write(minChanges(str, n)); </script> |
Output:
2
Time Complexity: O(n), where n is the size of the given string
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!
