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 = 3
Output: 2
Explanation:
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 = 3
Output: 4
Explanation:
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 countbool 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 searchint 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 codeint 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'sclass 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 countdef 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 searchdef 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 coden = 5m = 3arr = [0] * nprint(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'susing 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 countfunction 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 searchfunction 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> |
2
Time Complexity: O(n*log(n)), The main part of the algorithm is binary search that takes O(log n) time. The check function has a loop that runs until the end of the array, and in the worst case, it can run n/d times, where d is the current distance being checked. Therefore, the time complexity of the check function is O(n/d). Since binary search is executed log n times, the overall time complexity of the algorithm is O(n*log n).
Auxiliary Space: O(1), The space complexity of the algorithm is O(1) since the memory usage is constant, and it does not depend on the input size. The input array is not modified, and the function uses only a few variables to store intermediate results. Therefore, the space complexity of the algorithm is constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
