Given a binary array arr[]. The task is to find the position of any 0 in arr[] such that the distance between two set bits is maximized.
Examples
Input: arr = [1, 0, 0, 0, 1, 0, 1]
Output: 2
Explanation: Flip the bit at arr[2]
Input: arr = [1, 0, 0, 0]
Output: 3
Approach: The problem can be solved by finding the longest distance between adjacent set bits with some variation. Follow the steps below to solve the given problem.
- For all distances between adjacent set bits, find the maximum one and store its half as one of the required answers.
- Then find the distance between distance between 0 and the first set bit, and between index N-1 and last set bit.
- Find the overall maximum as the required answer.
- Print the answer found at the end.
Below is the implementation of the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum distance between any // two set bits after flipping one bit int maxDistToClosest1(vector< int >& arr) { // The size of the array int n = arr.size(), ans = 0; int temp = 1, setbit = 0; // Iterate through the array for ( int i = 1; i < n; i++) { if (arr[i] == 1) { if (setbit == 0 && arr[0] == 0) ans = max(ans, temp); else ans = max(ans, temp / 2); setbit = 1; temp = 0; } temp++; } ans = arr[n - 1] == 0 ? max(temp - 1, ans) : max(temp / 2, ans); // Return the answer found return ans; } // Driver Code int main() { vector< int > arr = { 1, 0, 0, 0, 1, 0, 1 }; // Function Call cout << maxDistToClosest1(arr); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the maximum distance between any // two set bits after flipping one bit static int maxDistToClosest1( int arr[]) { // The size of the array int n = arr.length, ans = 0 ; int temp = 1 , setbit = 0 ; // Iterate through the array for ( int i = 1 ; i < n; i++) { if (arr[i] == 1 ) { if (setbit == 0 && arr[ 0 ] == 0 ) ans = Math.max(ans, temp); else ans = Math.max(ans, temp / 2 ); setbit = 1 ; temp = 0 ; } temp++; } ans = arr[n - 1 ] == 0 ? Math.max(temp - 1 , ans) : Math.max(temp / 2 , ans); // Return the answer found return ans; } // Driver Code public static void main (String[] args) { int arr[] = { 1 , 0 , 0 , 0 , 1 , 0 , 1 }; // Function Call System.out.print(maxDistToClosest1(arr)); } } // This code is contributed by hrithikgarg03188. |
Python
# Python program for above approach # Function to find the maximum distance between any # two set bits after flipping one bit def maxDistToClosest1(arr): # The size of the array n = len (arr) ans = 0 temp = 1 setbit = 0 # Iterate through the array for i in range ( 1 , n): if (arr[i] = = 1 ): if (setbit = = 0 and arr[ 0 ] = = 0 ): ans = max (ans, temp) else : ans = max (ans, temp / / 2 ) setbit = 1 temp = 0 temp + = 1 if (arr[n - 1 ] = = 0 ): ans = max (temp - 1 , ans) else : ans = max (temp / / 2 , ans) # Return the answer found return ans # Driver Code arr = [ 1 , 0 , 0 , 0 , 1 , 0 , 1 ] # Function Call print (maxDistToClosest1(arr)) # This code is contributed by Samim Hossain Mondal. |
C#
// C# program for above approach using System; class GFG { // Function to find the maximum distance between any // two set bits after flipping one bit static int maxDistToClosest1( int [] arr) { // The size of the array int n = arr.Length, ans = 0; int temp = 1, setbit = 0; // Iterate through the array for ( int i = 1; i < n; i++) { if (arr[i] == 1) { if (setbit == 0 && arr[0] == 0) ans = Math.Max(ans, temp); else ans = Math.Max(ans, temp / 2); setbit = 1; temp = 0; } temp++; } ans = arr[n - 1] == 0 ? Math.Max(temp - 1, ans) : Math.Max(temp / 2, ans); // Return the answer found return ans; } // Driver Code public static int Main() { int [] arr = { 1, 0, 0, 0, 1, 0, 1 }; // Function Call Console.Write(maxDistToClosest1(arr)); return 0; } } // This code is contributed by Taranpreet |
Javascript
<script> // JavaScript program for above approach // Function to find the maximum distance between any // two set bits after flipping one bit const maxDistToClosest1 = (arr) => { // The size of the array let n = arr.length, ans = 0; let temp = 1, setbit = 0; // Iterate through the array for (let i = 1; i < n; i++) { if (arr[i] == 1) { if (setbit == 0 && arr[0] == 0) ans = Math.max(ans, temp); else ans = Math.max(ans, parseInt(temp / 2)); setbit = 1; temp = 0; } temp++; } ans = arr[n - 1] == 0 ? Math.max(temp - 1, ans) : Math.max(parseInt(temp / 2), ans); // Return the answer found return ans; } // Driver Code let arr = [1, 0, 0, 0, 1, 0, 1]; // Function Call document.write(maxDistToClosest1(arr)); // This code is contributed by rakeshsahni </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!