Minimum Number of K consecutive Bit Flips

Problem Statement: Given a binary string and integer k, the task is to find the minimum number of flips required such that every substring of length k contains at least one set bit.

Examples:

Example 1:
Input: str = “010” , k=1
Output: 2
Explanation:  flip str[0] and then str[2]

Example 2:
Input: str = “110” , k=2
Output: 0

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Brute Force Approach

The brute force approach is to traverse the given string n-k times and for every index, traverse the nested loop for k times and check whether the given part of the string contains at least one.

If it is, this means no flips are required. Otherwise, the flip is required.

Let us understand using the given example

Let us understand using  the given example

For eg - given string as “01000001” , k=3

For 0th index of 01000001
010 -> It has at-least one present. So, no flipping required.

For 1st index of 01000001
100-> It has at-least one present. So, no flipping required.

For 2nd index of 01000001
000-> It do not have at-least one present. 
So one flipping required.

Flipping will be done at last index of current substring, 
since this ‘1’ can be used for other strings also.
Similarly in further steps, we will count the 
number of flips and return the count

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
// Brute force approach
int findminflips(string str,int k)
{
    int flips=0;
    for(int i=0;i<str.length()-k;i++)
    {
        bool flag=false;
        for(int j=0;j<k;j++)
        {
            if(str[j+i]=='1')
            flag=true;
        }
        if(flag==false) // this means '1' is not present
        {
            str[i+k-1]='1';
            flips++;
        }
    }
    return flips;
}
int main()
{
    string str="0100001";
    int k=3;
    cout<<"The minimum number of flips required is: "
        <<findminflips(str,k)<<endl;
    return 0;
}

Output:

The minimum number of flips required is: 1

Time Complexity: O(n*k)

Space complexity: O(1)

Java Code

import java.util.*;
public class Main {
  // Brute force approach
  public static int findminflips(char[] str, int n, int k) {
    int flips = 0;
    for (int i = 0; i < n - k; i++) {
      boolean flag = false;
      for (int j = 0; j < k; j++) {
        if (str[i + j] == '1')
          flag = true;
      }
      if (flag == false) // this means '1' is not present
      {
        str[i + k - 1] = '1';
        flips++;
      }
    }
    return flips;
  }
  public static void main(String args[]) {
    String str = "0100001";
    int n = 7;
    int k = 3;
    System.out.print("The minimum number of flips required is: ");
    System.out.println(findminflips(str.toCharArray(), n, k));
  }
}

Output:

The minimum number of flips required is: 1

Time Complexity: O(n*k)

Space complexity: O(1)

Solution 2: Optimized Way – Sliding Window Technique

Approach:

This technique is based on the sliding window in the current string.

Let us understand it

“01000001” , k=3 -> for the given window 
                    atleast one ‘1’ is present
“01000001” , k=3 -> for the given window 
                    atleast one ‘1’ is present
“01000001” , k=3 -> for the given window 
                    atleast one ‘1’ is not present.
So flip the latest position 0 to 1 so that it 
can be usable by other next substrings

Flips =1
String becomes = “01001001” 
“01001001” , k=3 -> for the given window 
                    atleast one ‘1’ is present
“01001001” , k=3 -> for the given window 
                    atleast one ‘1’ is present          
“01001001” , k=3 -> for the given window 
                    atleast one ‘1’ is present

So finally flips  = 1 required  in the given string

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
// Sliding window technique
int findminflips(string str,int k)
{
    int flips=0;
    bool flag=false;
    int prevposof1=-1;
    for(int i=0;i<k;i++)
    {
        if(str[i]=='1')
        {
        prevposof1=i;
        flag=true;
        }
    }
    if(flag==false)
    {
        flips++;
        prevposof1=k-1;
        str[k-1]='1';
    }
    for(int i=k;i<str.length();i++)
    {
        if(str[i]=='1')
        prevposof1=i;
 
        // if currently i am standing at '0'
        else if(prevposof1>i-k)
        {
             // no flip is required
        }
        else
        {
            flips++;
            prevposof1=i;
        }
 
    }
    return flips;
}

int main()
{
    string str="0100001";
    int k=3;
    cout<<"The minimum number of flips required is: "
        <<findminflips(str,k)<<endl;
    return 0;
}

Output:

The minimum number of flips required is: 1

Time Complexity – O(N)

Space complexity – O(1)

Java Code

import java.util.*;
public class Main {
  // Sliding window technique
  public static int findminflips(char[] str, int n, int k) {
    int flips = 0;
    boolean flag = false;
    int prevposof1 = -1;
    for (int i = 0; i < k; i++) {
      if (str[i] == '1') {
        prevposof1 = i;
        flag = true;
      }
    }
    if (flag == false) {
      flips++;
      prevposof1 = k - 1;
    }
    for (int i = k; i < n; i++) {
      if (str[i] == '1')
        prevposof1 = i;
 
      // if currently i am standing at '0'
      else if (prevposof1 > i - k) {
        // no flip is required
      } else {
        flips++;
        prevposof1 = i;
      }
 
    }
 
    return flips;
  }
  public static void main(String args[]) {
    String str = "0100001";
    int n = 7;
    int k = 3;
    System.out.print("The minimum number of flips required is: ");
    System.out.println(findminflips(str.toCharArray(), n, k));
  }
}

Output:

The minimum number of flips required is: 1

Time Complexity – O(N)

Space complexity – O(1)

Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article