Dados dos arreglos binarios L1[] y L2[] , cada uno de tamaño N , la tarea es minimizar la cantidad de elementos restantes del arreglo después de realizar las siguientes operaciones:
- Si el primer elemento de ambas arrays es el mismo, elimínelo de ambas arrays.
- De lo contrario, elimine el primer elemento de L1[] y agréguelo al final de la array L1[] .
Ejemplos:
Entrada: L1 = {1, 0, 1, 0}, L2 = {0, 1, 0, 1}
Salida: 0
Explicación:
L1[0] = 1, L2[0] = 0. Por lo tanto, L1[] modifica a {0, 1, 0, 1}.
Dado que L1[0] y L2[0] son iguales, ambos se eliminan de sus respectivas arrays.
Ahora, L1[] se modifica a {1, 0, 1} y L2 se modifica a {1, 0, 1}.
Para los siguientes tres pasos, el primer elemento de la array es igual. Por lo tanto, el recuento de elementos restantes es 0.Entrada: L1 = {1, 1, 0, 0}, L2 = {0, 0, 0, 1}
Salida: 2
Enfoque: La idea es almacenar el conteo de 1 s y 0 s en la array L1[] . Luego, mientras atraviesa la array L2[] , si se encuentra 1 , disminuya la cuenta de 1 s. De lo contrario, disminuya la cuenta de 0 s. En cualquier instante, si alguno de los recuentos se vuelve inferior a 0 , esto indica que después de ese índice en particular, no se puede eliminar ningún otro elemento. Siga los pasos a continuación para resolver el problema:
- Recorra la array L1[] y cuente el número de 0 s y 1 s y almacénelos en variables, digamos cero y uno respectivamente.
- Ahora, recorra la array L2[] y realice los siguientes pasos:
- Si el elemento actual de L2[] es 1 , entonces disminuya uno en 1 . De lo contrario, disminuya cero en 1 .
- Si en cualquier instante, uno o cero se vuelven negativos, almacene el índice en la variable ans y salga del ciclo .
- Después de completar los pasos anteriores, imprima el valor de (N – ans) como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
2
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por promaroy20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA