Given a binary array arr[], the task is to find the number of operations required to remove all 1s from the adjacent left of 0s. In each operation, all 1s, to the immediate left of a 0, are changed to 0.
Examples:
Input: arr[] = { 1, 0, 0, 1, 1, 0 }
Output: 2
Explanation:
Operation 1: Change in index 0 and 4. arr[] = { 0, 0, 0, 1, 0, 0 }
Operation 2: Change in index 3. arr[] = { 0, 0, 0, 0, 0, 0 }
No more operations required.Input: arr[] = { 0, 1, 0, 1 }
Output: 1
Explanation:
Operation 1: Change in index 1. arr[] = { 0, 0, 0, 1 }
No more operations required.
Approach: This problem can be solved using Greedy Approach. The idea is to calculate the maximum number of consecutive 1’s before 0 which gives the number of times the given operation needed to perform such that the array cannot be altered further.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number// of 1's before 0void noOfMoves(int arr[], int n){ int cnt = 0; int maxCnt = 0; // Traverse the array for (int i = 0; i < n; i++) { // If value is 1 if (arr[i] == 1) { cnt++; } else { // If consecutive 1 followed // by 0, then update the maxCnt if (cnt != 0) { maxCnt = max(maxCnt, cnt); cnt = 0; } } } // Print the maximum consecutive 1's // followed by 0 cout << maxCnt << endl;}// Driver Codeint main(){ int arr[] = { 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call noOfMoves(arr, N); int arr1[] = { 1, 0, 1, 0, 1, 0, 1, 0 }; N = sizeof(arr) / sizeof(arr[0]); // Function Call noOfMoves(arr1, N); return 0;} |
Java
// Java implementation of the above approachclass GFG{// Function to find the maximum number// of 1's before 0static void noOfMoves(int arr[], int n){ int cnt = 0; int maxCnt = 0; // Traverse the array for (int i = 0; i < n; i++) { // If value is 1 if (arr[i] == 1) { cnt++; } else { // If consecutive 1 followed // by 0, then update the maxCnt if (cnt != 0) { maxCnt = Math.max(maxCnt, cnt); cnt = 0; } } } // Print the maximum consecutive 1's // followed by 0 System.out.print(maxCnt +"\n");}// Driver Codepublic static void main(String[] args){ int arr[] = { 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1 }; int N = arr.length; // Function Call noOfMoves(arr, N); int arr1[] = { 1, 0, 1, 0, 1, 0, 1, 0 }; N = arr1.length; // Function Call noOfMoves(arr1, N);}}// This code is contributed by 29AjayKumar |
Python 3
# Python 3 implementation of the above approach# Function to find the maximum number# of 1's before 0def noOfMoves(arr,n): cnt = 0 maxCnt = 0 # Traverse the array for i in range(n): # If value is 1 if (arr[i] == 1): cnt += 1 else: # If consecutive 1 followed # by 0, then update the maxCnt if (cnt != 0): maxCnt = max(maxCnt, cnt) cnt = 0 # Print the maximum consecutive 1's # followed by 0 print(maxCnt)# Driver Codeif __name__ == '__main__': arr = [0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1] N = len(arr) # Function Call noOfMoves(arr, N) arr1 = [1, 0, 1, 0, 1, 0, 1, 0] N = len(arr1) # Function Call noOfMoves(arr1, N)# This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the above approachusing System;public class GFG{ // Function to find the maximum number// of 1's before 0static void noOfMoves(int []arr, int n){ int cnt = 0; int maxCnt = 0; // Traverse the array for (int i = 0; i < n; i++) { // If value is 1 if (arr[i] == 1) { cnt++; } else { // If consecutive 1 followed // by 0, then update the maxCnt if (cnt != 0) { maxCnt = Math.Max(maxCnt, cnt); cnt = 0; } } } // Print the maximum consecutive 1's // followed by 0 Console.Write(maxCnt +"\n");} // Driver Codepublic static void Main(String[] args){ int []arr = { 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1 }; int N = arr.Length; // Function Call noOfMoves(arr, N); int []arr1 = { 1, 0, 1, 0, 1, 0, 1, 0 }; N = arr1.Length; // Function Call noOfMoves(arr1, N);}}// This code contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the above approach// Function to find the maximum number// of 1's before 0function noOfMoves(arr, n){ let cnt = 0; let maxCnt = 0; // Traverse the array for (let i = 0; i < n; i++) { // If value is 1 if (arr[i] == 1) { cnt++; } else { // If consecutive 1 followed // by 0, then update the maxCnt if (cnt != 0) { maxCnt = Math.max(maxCnt, cnt); cnt = 0; } } } // Print the maximum consecutive 1's // followed by 0 document.write( maxCnt + "<br>");}// Driver Code let arr = [ 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1 ]; let N = arr.length; // Function Call noOfMoves(arr, N); let arr1 = [ 1, 0, 1, 0, 1, 0, 1, 0 ]; N = arr.length; // Function Call noOfMoves(arr1, N);//This code is contributed by Mayank Tyagi</script> |
Output:
4 1
Time Complexity: O(N), where N is the length of the array.
Auxiliary Space: O(1), as constant space is required.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
