# Maximize distance between any two consecutive 1’s after flipping M 0’s

Given the size of a binary array consisting of 0’s only as **n** and an integer **m** which is the number of flips allowed from 0’s o 1’s; the task is to maximize the distance between any two consecutive 1’s after flipping **m** 0’s to 1’s.

**Examples:**

Input:n = 5, m = 3Output:2Explanation:

The initial array is arr = {0, 0, 0, 0, 0},

The final array is arr = {1, 0, 1, 0, 1},

So distance between two consecutive 1’s is 2.Input:n = 9, m = 3Output:4Explanation:

The initial array is arr = {0, 0, 0, 0, 0, 0, 0, 0, 0},

The final array is arr = {1, 0, 0, 0, 1, 0, 0, 0, 1},

so distance between two consecutive 1’s 4.

**Approach:**

- We can simply binary search on the distance between any two consecutive ones and check whether we can flip
**m**numbers of zero’s to one’s. - First, we set low = 1, and high = n – 1,
- Then check whether mid = (low+high)/2 will be a suitable distance or not.
- If it is then the updated answer is mid, else decrease high = mid – 1.

Below is the implementation of the above approach:

## CPP

`// C++ program to Maximize distance between` `// any two consecutive 1's after flipping M 0's` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return the count` `bool` `check(` `int` `arr[], ` `int` `n, ` `int` `m, ` `int` `d)` `{` ` ` `// Flipping zeros at distance "d"` ` ` `int` `i = 0;` ` ` `while` `(i < n && m > 0) {` ` ` `m--;` ` ` `i += d;` ` ` `}` ` ` `return` `m == 0 ? ` `true` `: ` `false` `;` `}` `// Function to implement` `// binary search` `int` `maximumDistance(` `int` `arr[], ` `int` `n, ` `int` `m)` `{` ` ` `int` `low = 1, high = n - 1;` ` ` `int` `ans = 0;` ` ` `while` `(low <= high) {` ` ` `int` `mid = (low + high) / 2;` ` ` `// Check for valid distance i.e mid` ` ` `bool` `flag = check(arr, n, m, mid);` ` ` `if` `(flag) {` ` ` `ans = mid;` ` ` `low = mid + 1;` ` ` `}` ` ` `else` `{` ` ` `high = mid - 1;` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `n = 5, m = 3;` ` ` `int` `arr[n] = { 0 };` ` ` `cout << maximumDistance(arr, n, m);` ` ` `return` `0;` `}` |

## Java

`// Java program to Maximize distance between` `// any two consecutive 1's after flipping M 0's` `class` `GFG` `{` ` ` `// Function to return the count` ` ` `static` `boolean` `check(` `int` `arr[], ` `int` `n, ` `int` `m, ` `int` `d)` ` ` `{` ` ` ` ` `// Flipping zeros at distance "d"` ` ` `int` `i = ` `0` `;` ` ` `while` `(i < n && m > ` `0` `)` ` ` `{` ` ` `m--;` ` ` `i += d;` ` ` `}` ` ` `return` `m == ` `0` `? ` `true` `: ` `false` `;` ` ` `}` ` ` `// Function to implement` ` ` `// binary search` ` ` `static` `int` `maximumDistance(` `int` `arr[], ` `int` `n, ` `int` `m)` ` ` `{` ` ` `int` `low = ` `1` `, high = n - ` `1` `;` ` ` `int` `ans = ` `0` `;` ` ` `while` `(low <= high)` ` ` `{` ` ` `int` `mid = (low + high) / ` `2` `;` ` ` `// Check for valid distance i.e mid` ` ` `boolean` `flag = check(arr, n, m, mid);` ` ` `if` `(flag)` ` ` `{` ` ` `ans = mid;` ` ` `low = mid + ` `1` `;` ` ` `}` ` ` `else` ` ` `{` ` ` `high = mid - ` `1` `;` ` ` `}` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `n = ` `5` `, m = ` `3` `;` ` ` `int` `arr[] = ` `new` `int` `[n];` ` ` `System.out.print(maximumDistance(arr, n, m));` ` ` `}` `}` `// This code is contributed by 29AjayKumar` |

## Python

`# Python3 program to Maximize distance between` `# any two consecutive 1's after flipping M 0's` `# Function to return the count` `def` `check(arr, n, m, d):` ` ` ` ` `# Flipping zeros at distance "d"` ` ` `i ` `=` `0` ` ` `while` `(i < n ` `and` `m > ` `0` `):` ` ` `m ` `-` `=` `1` ` ` `i ` `+` `=` `d` ` ` `if` `m ` `=` `=` `0` `:` ` ` `return` `True` ` ` `return` `False` `# Function to implement` `# binary search` `def` `maximumDistance(arr, n, m):` ` ` `low ` `=` `1` ` ` `high ` `=` `n ` `-` `1` ` ` `ans ` `=` `0` ` ` `while` `(low <` `=` `high):` ` ` `mid ` `=` `(low ` `+` `high) ` `/` `/` `2` ` ` `# Check for valid distance i.e mid` ` ` `flag ` `=` `check(arr, n, m, mid)` ` ` `if` `(flag) :` ` ` `ans ` `=` `mid` ` ` `low ` `=` `mid ` `+` `1` ` ` `else` `:` ` ` `high ` `=` `mid ` `-` `1` ` ` `return` `ans` `# Driver code` `n ` `=` `5` `m ` `=` `3` `arr ` `=` `[` `0` `] ` `*` `n` `print` `(maximumDistance(arr, n, m))` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program to Maximize distance between` `// any two consecutive 1's after flipping M 0's` `using` `System;` `class` `GFG` `{` ` ` `// Function to return the count` ` ` `static` `bool` `check(` `int` `[]arr, ` `int` `n, ` `int` `m, ` `int` `d)` ` ` `{` ` ` ` ` `// Flipping zeros at distance "d"` ` ` `int` `i = 0;` ` ` `while` `(i < n && m > 0)` ` ` `{` ` ` `m--;` ` ` `i += d;` ` ` `}` ` ` `return` `m == 0 ? ` `true` `: ` `false` `;` ` ` `}` ` ` `// Function to implement` ` ` `// binary search` ` ` `static` `int` `maximumDistance(` `int` `[]arr, ` `int` `n, ` `int` `m)` ` ` `{` ` ` `int` `low = 1, high = n - 1;` ` ` `int` `ans = 0;` ` ` `while` `(low <= high)` ` ` `{` ` ` `int` `mid = (low + high) / 2;` ` ` `// Check for valid distance i.e mid` ` ` `bool` `flag = check(arr, n, m, mid);` ` ` `if` `(flag)` ` ` `{` ` ` `ans = mid;` ` ` `low = mid + 1;` ` ` `}` ` ` `else` ` ` `{` ` ` `high = mid - 1;` ` ` `}` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `int` `n = 5, m = 3;` ` ` `int` `[]arr = ` `new` `int` `[n];` ` ` `Console.Write(maximumDistance(arr, n, m));` ` ` `}` `}` `// This code is contributed by PrinciRaj1992` |

## Javascript

`<script>` `//Javascript program to Maximize distance between` `// any two consecutive 1's after flipping M 0's` `// Function to return the count` `function` `check(arr, n, m, d)` `{` ` ` `// Flipping zeros at distance "d"` ` ` `var` `i = 0;` ` ` `while` `(i < n && m > 0) {` ` ` `m--;` ` ` `i += d;` ` ` `}` ` ` `return` `m == 0 ? ` `true` `: ` `false` `;` `}` `// Function to implement` `// binary search` `function` `maximumDistance(arr, n, m)` `{` ` ` `var` `low = 1, high = n - 1;` ` ` `var` `ans = 0;` ` ` `while` `(low <= high) {` ` ` `var` `mid = parseInt( (low + high) / 2);` ` ` `// Check for valid distance i.e mid` ` ` `var` `flag = check(arr, n, m, mid);` ` ` `if` `(flag) {` ` ` `ans = mid;` ` ` `low = mid + 1;` ` ` `}` ` ` `else` `{` ` ` `high = mid - 1;` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` `var` `n = 5, m = 3;` `var` `arr = ` `new` `Array(n);` `arr.fill(0);` `document.write( maximumDistance(arr, n, m));` `//This code is contributed by SoumikMondal` `</script>` |

**Output:**

2

**Time Complexity:** O(n*log(n))

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.