Given two binary arrays L1[] and L2[], each of size N, the task is to minimize the count of remaining array elements after performing the following operations:
- If the first element of both the arrays is same, then remove it from both the arrays.
- Otherwise, remove the first element from L1[] and append it at the end of the array L1[].
Examples:
Input: L1 = {1, 0, 1, 0}, L2 = {0, 1, 0, 1}
Output: 0
Explanation:
L1[0] = 1, L2[0] = 0. Therefore, L1[] modifies to {0, 1, 0, 1}.
Since L1[0] and L2[0] are equal, both are removed from their respective arrays.
Now, L1[] modifies to {1, 0, 1} and L2 modifies to {1, 0, 1}.
For the next three steps, the first array element are equal. Therefore, the count of remaining elements is 0.Input: L1 = {1, 1, 0, 0}, L2 = {0, 0, 0, 1}
Output: 2
Approach: The idea is to store the count of 1s and 0s in the array L1[]. Then, while traversing the array L2[], if 1 is encountered, decrement the count of 1s. Otherwise, decrement the count of 0s. At any instant, if either of the counts becomes less than 0, then this indicates that after that particular index, no further element can be removed. Follow the steps below to solve the problem:
- Traverse the array L1[] and count the number of 0s and 1s and store them in variables, say zero and one respectively.
- Now, traverse the array L2[] and perform the following steps:
- If the current element of L2[] is 1, then decrement one by 1. Otherwise, decrement zero by 1.
- If at any instant, either one or zero becomes negative, store the index in variable ans and break out of the loop.
- After completing the above steps, print the value of (N – ans) as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the remaining// elements in the arraysvoid countRemainingElements( int L1[], int L2[], int n){ // Stores the count of 1s in L1[] int one = 0; // Store the count of 0s in L2[] int zero = 0; // Traverse the array L1[] for (int i = 0; i < n; i++) { // If condition is true if (L1[i] == 1) // Increment one by 1 one++; else // Increment zero by 1 zero++; } // Stores the index after which no // further removals are possible int ans = n; // Traverse the array L2[] for (int i = 0; i < n; i++) { // If condition is true if (L2[i] == 1) { // Decrement one by 1 one--; // If one < 0, then break // out of the loop if (one < 0) { ans = i; break; } } else { // Decrement zero by 1 zero--; // If zero < 0, then // break out of loop if (zero < 0) { ans = i; break; } } } // Print the answer cout << n - ans;}// Driver Codeint main(){ int L1[] = { 1, 1, 0, 0 }; int L2[] = { 0, 0, 0, 1 }; int N = sizeof(L1) / sizeof(L1[0]); // Function Call countRemainingElements(L1, L2, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to count the remaining// elements in the arraysstatic void countRemainingElements(int[] L1, int[] L2, int n){ // Stores the count of 1s in L1[] int one = 0; // Store the count of 0s in L2[] int zero = 0; // Traverse the array L1[] for(int i = 0; i < n; i++) { // If condition is true if (L1[i] == 1) // Increment one by 1 one++; else // Increment zero by 1 zero++; } // Stores the index after which no // further removals are possible int ans = n; // Traverse the array L2[] for(int i = 0; i < n; i++) { // If condition is true if (L2[i] == 1) { // Decrement one by 1 one--; // If one < 0, then break // out of the loop if (one < 0) { ans = i; break; } } else { // Decrement zero by 1 zero--; // If zero < 0, then // break out of loop if (zero < 0) { ans = i; break; } } } // Print the answer System.out.println(n - ans);}// Driver Codepublic static void main(String[] args){ int[] L1 = { 1, 1, 0, 0 }; int[] L2 = { 0, 0, 0, 1 }; int N = L1.length; // Function Call countRemainingElements(L1, L2, N);}}// This code is contributed by Dharanendra L V |
C#
// C# program for the above approachusing System;class GFG{// Function to count the remaining// elements in the arraysstatic void countRemainingElements(int[] L1, int[] L2, int n){ // Stores the count of 1s in L1[] int one = 0; // Store the count of 0s in L2[] int zero = 0; // Traverse the array L1[] for(int i = 0; i < n; i++) { // If condition is true if (L1[i] == 1) // Increment one by 1 one++; else // Increment zero by 1 zero++; } // Stores the index after which no // further removals are possible int ans = n; // Traverse the array L2[] for(int i = 0; i < n; i++) { // If condition is true if (L2[i] == 1) { // Decrement one by 1 one--; // If one < 0, then break // out of the loop if (one < 0) { ans = i; break; } } else { // Decrement zero by 1 zero--; // If zero < 0, then // break out of loop if (zero < 0) { ans = i; break; } } } // Print the answer Console.WriteLine(n - ans);}// Driver Codestatic public void Main(){ int[] L1 = { 1, 1, 0, 0 }; int[] L2 = { 0, 0, 0, 1 }; int N = L1.Length; // Function Call countRemainingElements(L1, L2, N);}}// This code is contributed by Dharanendra L V |
Python3
# Python program for the above approach# Function to count the remaining# elements in the arraysdef countRemainingElements(L1, L2, n): # Stores the count of 1s in L1 one = 0; # Store the count of 0s in L2 zero = 0; # Traverse the array L1 for i in range(n): # If condition is True if (L1[i] == 1): # Increment one by 1 one += 1; else: # Increment zero by 1 zero += 1; # Stores the index after which no # further removals are possible ans = n; # Traverse the array L2 for i in range(n): # If condition is True if (L2[i] == 1): # Decrement one by 1 one -= 1; # If one < 0, then break # out of the loop if (one < 0): ans = i; break; else: # Decrement zero by 1 zero -= 1; # If zero < 0, then # break out of loop if (zero < 0): ans = i; break; # Print the answer print(n - ans);# Driver Codeif __name__ == '__main__': L1 = [ 1, 1, 0, 0 ]; L2 = [ 0, 0, 0, 1 ]; N = len(L1); # Function Call countRemainingElements(L1, L2, N);# This code is contributed by gauravrajput1 |
Javascript
<script>// JavaScript program for// the above approach // Function to count the remaining// elements in the arraysfunction countRemainingElements( L1, L2, n){ // Stores the count of 1s in L1[] let one = 0; // Store the count of 0s in L2[] let zero = 0; // Traverse the array L1[] for(let i = 0; i < n; i++) { // If condition is true if (L1[i] == 1) // Increment one by 1 one++; else // Increment zero by 1 zero++; } // Stores the index after which no // further removals are possible let ans = n; // Traverse the array L2[] for(let i = 0; i < n; i++) { // If condition is true if (L2[i] == 1) { // Decrement one by 1 one--; // If one < 0, then break // out of the loop if (one < 0) { ans = i; break; } } else { // Decrement zero by 1 zero--; // If zero < 0, then // break out of loop if (zero < 0) { ans = i; break; } } } // Print the answer document.write(n - ans);} // Driver Code let L1 = [ 1, 1, 0, 0 ]; let L2 = [ 0, 0, 0, 1 ]; let N = L1.length; // Function Call countRemainingElements(L1, L2, N); </script> |
Output:
2
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
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!