Given a binary string S, and an integer K, the task is to find the minimum number of flips required such that every substring of length K contains at least one ‘1’.
Examples:
Input: S = “10000001” K = 2
Output: 3
Explanation:
We need only 3 changes in string S ( at position 2, 4 and 6 ) so that the string contain at least one ‘1’ in every sub-string of length 2.
Input: S = “000000” K = 3
Output: 2
Explanation:
We need only 3 changes in string S ( at position 2 and 5 ) so that the string contain at least one ‘1’ in every sub-string of length 3.
Input: S = “111010111” K = 2
Output: 0
Naive Approach:
To solve the problem, the simplest approach is to iterate for each substring of length K and find the minimum number of flips required to satisfy the given condition.
Time complexity: O(N * K)
Space Complexity: O(1)
Efficient Approach:
The idea is to use Sliding Window Approach.
- Set a window size of K.
- Store the index of previous appearance of 1.
- If the current bit is unset and the difference between the current ith bit and the previous set bit exceeds K, set the current bit and store the current index as that of the previous set bit and proceed further.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count min flipsint CountMinFlips(string s, int n, int k){ // To store the count of minimum // flip required int cnt = 0; // To store the position of last '1' int prev = -1; for (int i = 0; i < k; i++) { // Track last position of '1' // in current window of size k if (s[i] == '1') { prev = i; } } // If no '1' is present in the current // window of size K if (prev == -1) { cnt++; // Set last index of window '1' s[k - 1] = '1'; // Track previous '1' prev = k - 1; } // Traverse the given string for (int i = k; i < n; i++) { // If the current bit is not set, // then the condition for flipping // the current bit if (s[i] != '1') { if (prev <= (i - k)) { // Set i'th index to '1' s[i] = '1'; // Track previous one prev = i; // Increment count cnt++; } } // Else update the prev set bit // position to current position else { prev = i; } } // Return the final count return (cnt);}// Driver Codeint main(){ // Given binary string string str = "10000001"; // Size of given string str int n = str.size(); // Window size int k = 2; // Function Call cout << CountMinFlips(str, n, k) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count min flipsstatic int CountMinFlips(char []s, int n, int k){ // To store the count of minimum // flip required int cnt = 0; // To store the position of last '1' int prev = -1; for(int i = 0; i < k; i++) { // Track last position of '1' // in current window of size k if (s[i] == '1') { prev = i; } } // If no '1' is present in the current // window of size K if (prev == -1) { cnt++; // Set last index of window '1' s[k - 1] = '1'; // Track previous '1' prev = k - 1; } // Traverse the given String for(int i = k; i < n; i++) { // If the current bit is not set, // then the condition for flipping // the current bit if (s[i] != '1') { if (prev <= (i - k)) { // Set i'th index to '1' s[i] = '1'; // Track previous one prev = i; // Increment count cnt++; } } // Else update the prev set bit // position to current position else { prev = i; } } // Return the final count return (cnt);}// Driver Codepublic static void main(String[] args){ // Given binary String String str = "10000001"; // Size of given String str int n = str.length(); // Window size int k = 2; // Function Call System.out.print(CountMinFlips( str.toCharArray(), n, k) + "\n");}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 code to count minimum no.# of flips required such that # every substring of length K# contain at least one '1'.# Function to count min flipsdef CountMinFlips(s, n, k): cnt = 0 prev = -1 for i in range(0, k): # Track last position of '1' # in current window of size k if(s[i]=='1'): prev = i; # means no '1' is present if(prev == -1): cnt += 1 # track previous '1' prev = k-1; for i in range(k, n): if(s[i] != '1'): if( prev <= (i-k) ): # track previous one prev = i; # increment count cnt += 1 else: prev = i return(cnt);# Driver codes = "10000001"n = len(s)k = 2print(CountMinFlips(s, n, k)) |
C#
// C# program for the above approachusing System;class GFG{// Function to count min flipsstatic int CountMinFlips(char []s, int n, int k){ // To store the count of minimum // flip required int cnt = 0; // To store the position of last '1' int prev = -1; for(int i = 0; i < k; i++) { // Track last position of '1' // in current window of size k if (s[i] == '1') { prev = i; } } // If no '1' is present in the current // window of size K if (prev == -1) { cnt++; // Set last index of window '1' s[k - 1] = '1'; // Track previous '1' prev = k - 1; } // Traverse the given String for(int i = k; i < n; i++) { // If the current bit is not set, // then the condition for flipping // the current bit if (s[i] != '1') { if (prev <= (i - k)) { // Set i'th index to '1' s[i] = '1'; // Track previous one prev = i; // Increment count cnt++; } } // Else update the prev set bit // position to current position else { prev = i; } } // Return the readonly count return (cnt);}// Driver Codepublic static void Main(String[] args){ // Given binary String String str = "10000001"; // Size of given String str int n = str.Length; // Window size int k = 2; // Function Call Console.Write(CountMinFlips( str.ToCharArray(), n, k) + "\n");}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// javascript program for the above approach// Function to count min flipsfunction CountMinFlips(s , n,k){ // To store the count of minimum // flip required var cnt = 0; // To store the position of last '1' var prev = -1; for(i = 0; i < k; i++) { // Track last position of '1' // in current window of size k if (s[i] == '1') { prev = i; } } // If no '1' is present in the current // window of size K if (prev == -1) { cnt++; // Set last index of window '1' s[k - 1] = '1'; // Track previous '1' prev = k - 1; } // Traverse the given String for(i = k; i < n; i++) { // If the current bit is not set, // then the condition for flipping // the current bit if (s[i] != '1') { if (prev <= (i - k)) { // Set i'th index to '1' s[i] = '1'; // Track previous one prev = i; // Increment count cnt++; } } // Else update the prev set bit // position to current position else { prev = i; } } // Return the final count return (cnt);}// Driver Code // Given binary String var str = "10000001"; // Size of given String str var n = str.length; // Window size var k = 2; // Function Call document.write(CountMinFlips( str, n, k) );// This code contributed by shikhasingrajput </script> |
Output:
3
Time complexity: O(N + K)
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!
