Minimize remaining array sizes by removing equal pairs of first array elements

0 0 6 minutes read

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 arrays
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
    cout << n - ans;
}
 
// Driver Code
int 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 approach
import java.io.*;
 
class GFG{
 
// Function to count the remaining
// elements in the arrays
static 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 Code
public 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 approach
using System;
 
class GFG{
 
// Function to count the remaining
// elements in the arrays
static 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 Code
static 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 arrays
def 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 Code
if __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 arrays
function 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:

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 zambiatek!