Given two binary arrays, A[] and B[] of size N respectively, the task is to find the number of elements in array A[] that will be left after performing the following operation until no elements can be deleted:
- If the starting elements of array A[] and B[] are equal, then delete both the elements.
- Otherwise, append the starting character of array A[] to the end of the array, A[], after removing it.
Examples:
Input: A[] = {1, 1, 0, 1}, B[] = {1, 0, 1, 1}, N = 4
Output: 0
Explanation:
The operations are performed as follows:
- A[0]( =1) = B[0]( =1): Delete the elements. Thereafter, the arrays are modified to {1, 0, 1} and {0, 1, 1} respectively.
- A[0](=1) != B[0](= 0): Shift the A[0] to the end of the array A[]. Thereafter, the arrays are modified to { 0, 1, 1} and {0, 1, 1} respectively.
- A[0]( =0) = B[0]( =0): Delete the elements. Thereafter, the arrays are modified to {1, 1} and {1, 1} respectively.
- A[0]( =1) = B[0]( =1): Delete the elements. Thereafter, the arrays are modified to {1} and {1} respectively.
- A[0]( =1) = B[0]( =1): Delete the elements. Thereafter, both arrays became empty.
Therefore, no elements are left in the array A[].
Input: A[] = {1, 0, 1, 1, 1, 1}, B[] = {1, 1, 0, 1, 0, 1}, N = 6
Output: 2
Approach: The given problem can be solved by removing the common 0s and 1s, and then counting the unique number of 0s and 1s in both arrays. Consider the following observations:
- The elements can be deleted as long as there is an element equal to the first element of B[] left in the array A[].
- It can also be observed that the order of elements of A[] can be easily changed.
- Therefore, the idea is to keep the count of the number of 0s and 1s left in A[] and if an element is encountered in B[] such that the same element is no longer present in A[], then no more operations can be performed.
Follow the steps below to solve the problem:
- Traverse the array, A[] and count the total number of 0s and 1s in variables and store them in variables, say zero and one respectively.
- Initialize a variable say count as 0 to store the total number of deletions performed.
- Traverse the array, B[] using the variable i and do the following:
- If B[i] is equal to 0 and zero>0, then increment the value of count by 1 and decrement zero by 1.
- Else, if B[i] is equal to 1 and one>0, then increment the value of count by 1 and decrement one by 1.
- Otherwise, break out of the loop as no more operations can further be performed.
- Finally, after completing the above steps, print the difference between N and count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate minimum size// of the array A[] after performing// the given operationsint minimumSizeAfterDeletion(int A[], int B[], int N){ // Stores the count of 0s and 1s int zero = 0, one = 0; // Stores the total deletions performed int count = 0; // Traverse the array A[] for (int i = 0; i < N; i++) { if (A[i] == 0) { zero++; } else { one++; } } // Traverse array B[] for (int i = 0; i < N; i++) { // If the B[i] is 0 and zero is // greater than 0 if (B[i] == 0 && zero > 0) { // Increment count by 1 count++; // Decrement zero by 1 zero--; } // Else if the B[i] is 1 and one is // greater than 0 else if (B[i] == 1 && one > 0) { // Increment count by 1 count++; // Decrement one by 1 one--; } // Otherwise else { break; } } // Return the answer return N - count;}// Driver Codeint main(){ // Given Input int A[] = { 1, 0, 1, 1, 1, 1 }; int B[] = { 1, 1, 0, 1, 0, 1 }; int N = 6; // Function Call cout << minimumSizeAfterDeletion(A, B, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to calculate minimum size// of the array A[] after performing// the given operationsstatic int minimumSizeAfterDeletion(int A[], int B[], int N){ // Stores the count of 0s and 1s int zero = 0, one = 0; // Stores the total deletions performed int count = 0; // Traverse the array A[] for(int i = 0; i < N; i++) { if (A[i] == 0) { zero++; } else { one++; } } // Traverse array B[] for(int i = 0; i < N; i++) { // If the B[i] is 0 and zero is // greater than 0 if (B[i] == 0 && zero > 0) { // Increment count by 1 count++; // Decrement zero by 1 zero--; } // Else if the B[i] is 1 and one is // greater than 0 else if (B[i] == 1 && one > 0) { // Increment count by 1 count++; // Decrement one by 1 one--; } // Otherwise else { break; } } // Return the answer return N - count;}// Driver Codepublic static void main(String[] args) { // Given Input int A[] = { 1, 0, 1, 1, 1, 1 }; int B[] = { 1, 1, 0, 1, 0, 1 }; int N = 6; // Function Call minimumSizeAfterDeletion(A, B, N); System.out.println(minimumSizeAfterDeletion(A, B, N));}}// This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach# Function to calculate minimum size# of the array A[] after performing# the given operationsdef minimumSizeAfterDeletion(A, B, N): # Stores the count of 0s and 1s zero = 0 one = 0 # Stores the total deletions performed count = 0 # Traverse the array A[] for i in range(N): if A[i] == 0: zero += 1 else: one += 1 # Traverse array B[] for i in range(N): # If the B[i] is 0 and zero is # greater than 0 if B[i] == 0 and zero > 0: # Increment count by 1 count += 1 # Decrement zero by 1 zero -= 1 # Else if the B[i] is 1 and one is # greater than 0 elif B[i] == 1 and one > 0: # Increment count by 1 count += 1 # Decrement one by 1 one -= 1 # Otherwise else: break # Return the answer return N - count# Driver code# Given inputA = [ 1, 0, 1, 1, 1, 1 ]B = [ 1, 1, 0, 1, 0, 1 ]N = 6# Function callprint(minimumSizeAfterDeletion(A, B, N))# This code is contributed by Parth Manchanda |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to calculate minimum size// of the array A[] after performing// the given operationsstatic int minimumSizeAfterDeletion(int []A, int []B, int N){ // Stores the count of 0s and 1s int zero = 0, one = 0; // Stores the total deletions performed int count = 0; // Traverse the array A[] for (int i = 0; i < N; i++) { if (A[i] == 0) { zero++; } else { one++; } } // Traverse array B[] for (int i = 0; i < N; i++) { // If the B[i] is 0 and zero is // greater than 0 if (B[i] == 0 && zero > 0) { // Increment count by 1 count++; // Decrement zero by 1 zero--; } // Else if the B[i] is 1 and one is // greater than 0 else if (B[i] == 1 && one > 0) { // Increment count by 1 count++; // Decrement one by 1 one--; } // Otherwise else { break; } } // Return the answer return N - count;}// Driver Codepublic static void Main(){ // Given Input int []A = { 1, 0, 1, 1, 1, 1 }; int []B = { 1, 1, 0, 1, 0, 1 }; int N = 6; // Function Call Console.Write(minimumSizeAfterDeletion(A, B, N));}}// This code is contributed by ipg2016107. |
Javascript
<script>// Javascript program for the above approach// Function to calculate minimum size// of the array A[] after performing// the given operationsfunction minimumSizeAfterDeletion(A, B, N){ // Stores the count of 0s and 1s var zero = 0, one = 0; // Stores the total deletions performed var count = 0; // Traverse the array A[] for(var i = 0; i < N; i++) { if (A[i] == 0) { zero++; } else { one++; } } // Traverse array B[] for(var i = 0; i < N; i++) { // If the B[i] is 0 and zero is // greater than 0 if (B[i] == 0 && zero > 0) { // Increment count by 1 count++; // Decrement zero by 1 zero--; } // Else if the B[i] is 1 and one is // greater than 0 else if (B[i] == 1 && one > 0) { // Increment count by 1 count++; // Decrement one by 1 one--; } // Otherwise else { break; } } // Return the answer return N - count;}// Driver Code // Given Input var A = [ 1, 0, 1, 1, 1, 1 ]; var B = [ 1, 1, 0, 1, 0, 1 ]; var N = 6; // Function Call minimumSizeAfterDeletion(A, B, N); document.write(minimumSizeAfterDeletion(A, B, N));// This code is contributed by shivanisinghss2110</script> |
Output
2
Time Complexity: O(N), as we are using a loop to traverse N times so it will cost us O(N) time.
Auxiliary Space: O(1), as we are not using any extra space.