Minimum time required to cover a Binary Array
Given an integer N which represents the size of a boolean array that is initially filled with 0, and also given an array arr[] of size K consisting of (1-based) indices at which ‘1’ are present in the boolean array. Now, at one unit of time the adjacent cells of the arr[i] in the boolean array become 1 that is 010 becomes 111. Find the minimum time required to convert the whole array into 1s.
Examples:
Input : N = 5, arr[] = {1, 4}
Output : 1
Explanation:
Initially the boolean array is of size 5 filled with 5 zeros. arr[] represents places at which 1 is present in the boolean array. Therefore, the boolean array becomes 10010.
Now, at time (t) = 1, the 0s at 3rd and 5th position becomes 1 => 10111 and at the same time, 0 at 2nd position becomes 1 => 11111. All the 1s initially increment their adjacent 0s at the same moment of time. So at t=1, the string gets converted to all 1s.
Input : N=7, arr[] = {1, 7}
Output : 3
Explanation:
At time (t) = 1, 1000001 becomes 1100011
At time (t) = 2, 1100011 becomes 1110111
At time (t) = 3, 1110111 becomes 1111111
Hence, minimum time is 3 to change the binary array into 1.
Approach:
To solve the problem mentioned above we have to observe that we need to find the longest segment of zeroes until 1 appears. For example, for a binary number 00010000010000, the longest segment of 0s is from 4th to 10th position. Now, observe that there are 5 0s between the indices which is an odd number. Hence, we can conclude that to cover 5 zeros we need 5/2 + 1 that is 3 units of time because all the other segments will get filled in less than or equal to 3 units of time.
- If the longest zero segments are odd then we can conclude that x/2 + 1 unit of time is required where x is the number of 0s in the longest segment.
- If the longest zero segments are even then we can conclude that x/2 units of time are required where x is the number of 0s in the longest segment.
We can calculate the maximum length contiguous segment until 1 occurs in the boolean array and return the answer depends upon whether the length is odd or even.
Below is the implementation of the above approach:
C++
// CPP implementation to find the // Minimum time required to cover a Binary Array #include <bits/stdc++.h> using namespace std; // function to calculate the time int solve(vector< int > arr, int n) { int k = arr.size(); // Map to mark or store the binary values bool mp[n + 2]; // Firstly fill the boolean // array with all zeroes for ( int i = 0; i <= n; i++) { mp[i] = 0; } // Mark the 1s for ( int i = 0; i < k; i++) { mp[arr[i]] = 1; } // Number of 0s until first '1' occurs int leftSegment = arr[0] - 1; // Maximum Number of 0s in between 2 '1's. for ( int i = 1; i < k; i++) { leftSegment = max(leftSegment, arr[i] - arr[i - 1] - 1); } // Number of 0s from right until first '1' occurs int rightSegment = n - arr[k - 1]; // Return maximum from left and right segment int maxSegment = max(leftSegment, rightSegment); int tim; // check if count is odd if (maxSegment & 1) tim = (maxSegment / 2) + 1; // check ifcount is even else tim = maxSegment / 2; // return the time return tim; } // driver code int main() { // initialise N int N = 5; // array initialisation vector< int > arr = { 1, 4 }; cout << solve(arr, N); } |
Java
// Java implementation to find the // Minimum time required to cover a Binary Array class GFG { // function to calculate the time static int solve( int []arr, int n) { int k = arr.length; // Map to mark or store the binary values int mp[] = new int [n + 2 ]; // Firstly fill the boolean // array with all zeroes for ( int i = 0 ; i <= n; i++) { mp[i] = 0 ; } // Mark the 1s for ( int i = 0 ; i < k; i++) { mp[arr[i]] = 1 ; } // Number of 0s until first '1' occurs int leftSegment = arr[ 0 ] - 1 ; // Maximum Number of 0s in between 2 '1's. for ( int i = 1 ; i < k; i++) { leftSegment = Math.max(leftSegment, arr[i] - arr[i - 1 ] - 1 ); } // Number of 0s from right until first '1' occurs int rightSegment = n - arr[k - 1 ]; // Return maximum from left and right segment int maxSegment = Math.max(leftSegment, rightSegment); int tim; // check if count is odd if ((maxSegment & 1 ) == 1 ) tim = (maxSegment / 2 ) + 1 ; // check ifcount is even else tim = maxSegment / 2 ; // return the time return tim; } // driver code public static void main (String[] args) { // initialise N int N = 5 ; // array initialisation int arr[] = { 1 , 4 }; System.out.println(solve(arr, N)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation to find the # Minimum time required to cover a Binary Array # function to calculate the time def solve(arr, n) : k = len (arr) # Map to mark or store the binary values # Firstly fill the boolean # array with all zeroes mp = [ False for i in range (n + 2 )] # Mark the 1s for i in range (k) : mp[arr[i]] = True # Number of 0s until first '1' occurs leftSegment = arr[ 0 ] - 1 # Maximum Number of 0s in between 2 '1's. for i in range ( 1 ,k) : leftSegment = max (leftSegment, arr[i] - arr[i - 1 ] - 1 ) # Number of 0s from right until first '1' occurs rightSegment = n - arr[k - 1 ] # Return maximum from left and right segment maxSegment = max (leftSegment, rightSegment); tim = 0 # check if count is odd if (maxSegment & 1 ) : tim = (maxSegment / / 2 ) + 1 # check ifcount is even else : tim = maxSegment / / 2 # return the time return tim # Driver code # initialise N N = 5 # array initialisation arr = [ 1 , 4 ] print (solve(arr, N)) # This code is contributed by Sanjit_Prasad |
C#
// C# implementation to find the // Minimum time required to cover // a Binary Array using System; class GFG{ // Function to calculate the time static int solve( int [] arr, int n) { int k = arr.Length; // Map to mark or store the binary values int [] mp = new int [n + 2]; // Firstly fill the boolean // array with all zeroes for ( int i = 0; i <= n; i++) { mp[i] = 0; } // Mark the 1s for ( int i = 0; i < k; i++) { mp[arr[i]] = 1; } // Number of 0s until first '1' occurs int leftSegment = arr[0] - 1; // Maximum Number of 0s in between 2 '1's. for ( int i = 1; i < k; i++) { leftSegment = Math.Max(leftSegment, arr[i] - arr[i - 1] - 1); } // Number of 0s from right until first '1' occurs int rightSegment = n - arr[k - 1]; // Return maximum from left and right segment int maxSegment = Math.Max(leftSegment, rightSegment); int tim; // Check if count is odd if ((maxSegment & 1) == 1) tim = (maxSegment / 2) + 1; // Check ifcount is even else tim = maxSegment / 2; // Return the time return tim; } // Driver code public static void Main () { // Initialise N int N = 5; // Array initialisation int [] arr = { 1, 4 }; Console.Write(solve(arr, N)); } } // This code is contributed by chitranayal |
Javascript
<script> // JavaScript implementation to find the // Minimum time required to cover a Binary Array // function to calculate the time function solve(arr, n) { let k = arr.length; // Map to mark or store the binary values let mp = Array.from({length: n+2}, (_, i) => 0); // Firstly fill the boolean // array with all zeroes for (let i = 0; i <= n; i++) { mp[i] = 0; } // Mark the 1s for (let i = 0; i < k; i++) { mp[arr[i]] = 1; } // Number of 0s until first '1' occurs let leftSegment = arr[0] - 1; // Maximum Number of 0s in between 2 '1's. for (let i = 1; i < k; i++) { leftSegment = Math.max(leftSegment, arr[i] - arr[i - 1] - 1); } // Number of 0s from right until first '1' occurs let rightSegment = n - arr[k - 1]; // Return maximum from left and right segment let maxSegment = Math.max(leftSegment, rightSegment); let tim; // check if count is odd if ((maxSegment & 1) == 1) tim = (maxSegment / 2) + 1; // check ifcount is even else tim = maxSegment / 2; // return the time return tim; } // Driver Code // initialise N let N = 5; // array initialisation let arr = [ 1, 4 ]; document.write(solve(arr, N)); </script> |
1
Time Complexity: O(N)
Auxiliary Space: O(N)