fork download
copy 
  1. // C++ program for the above approach
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // Function to count min flips
  6. int CountMinFlips(string s, int n,
  7.                   int k)
  8. {
  9.  
  10.     // To store the count of minimum
  11.     // flip required
  12.     int cnt = 0;
  13.  
  14.     // To store the position of last '1'
  15.     int prev = -1;
  16.  
  17.     for (int i = 0; i < k; i++) {
  18.  
  19.         // Track last position of '1'
  20.         // in current window of size k
  21.         if (s[i] == '1') {
  22.             prev = i;
  23.         }
  24.     }
  25.  
  26.     // If no '1' is present in the current
  27.     // window of size K
  28.     if (prev == -1) {
  29.         cnt++;
  30.  
  31.         // Set last index of window '1'
  32.         s[k - 1] = '1';
  33.  
  34.         // Track previous '1'
  35.         prev = k - 1;
  36.     }
  37.  
  38.     // Traverse the given string
  39.     for (int i = k; i < n; i++) {
  40.  
  41.         // If the current bit is not set,
  42.         // then the condition for flipping
  43.         // the current bit
  44.         if (s[i] != '1') {
  45.             if (prev <= (i - k)) {
  46.  
  47.                 // Set i'th index to '1'
  48.                 s[i] = '1';
  49.  
  50.                 // Track previous one
  51.                 prev = i;
  52.  
  53.                 // Increment count
  54.                 cnt++;
  55.             }
  56.         }
  57.  
  58.         // Else update the prev set bit
  59.         // position to current position
  60.         else {
  61.             prev = i;
  62.         }
  63.     }
  64.  
  65.     // Return the final count
  66.     return (cnt);
  67. }
  68.  
  69. // Driver Code
  70. int main()
  71. {
  72.     // Given binary string
  73.     string str = "00010110";
  74.  
  75.     // Size of given string str
  76.     int n = str.size();
  77.  
  78.     // Window size
  79.     int k = 2;
  80.  
  81.     // Function Call
  82.     cout << CountMinFlips(str, n, 3)
  83.          << endl;
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
stdout
copy 
1
https://ideone.com/tyabH4
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!