Encuentre si 0 se elimina más o 1 eliminando el elemento central si el triplete consecutivo es divisible por 3 en la array binaria dada

 Dada una array binaria a[] de tamaño N de 1 y 0 . La tarea es eliminar un elemento si a[i-1]+a[i]+a[i+1] es divisible por 3 . Imprima 1 si se eliminan más números de 1 que 0 , de lo contrario imprima 0 .

Ejemplos: 

Entrada : a[] = { 1, 1, 1, 0, 1, 0, 0}
Salida : 1
Explicación: elimine el segundo 1 de la izquierda ya que es el único ‘1’ para el que (a[i]+a [i-1]+a[i+1]) %3==0. Entonces imprima 1.

Entrada : a[] = { 1, 1}
Salida : 0 
Explicación : No es posible eliminarlo, así que imprima 0.

 

Enfoque: La idea se basa en la observación de que si ambos vecinos son iguales al elemento actual porque si (a[i]=a[i-1]=a[i+1]) entonces la suma siempre será divisible por 3 . Digamos que A almacena el número de 1 eliminados y B almacena el número de 0 eliminados. Si el i-ésimo elemento es igual a los vecinos, entonces si a[i] =1 , incrementa A , de lo contrario B. Si el conteo de A es mayor que B , imprima 1 , de lo contrario imprima 2=0 . Siga los pasos a continuación para resolver el problema:

  • Inicialice las variables A y B como 0 para almacenar el número de 1 y 0 eliminado.
  • Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
    • Si a[i-1], a[i] y a[i+1] son ​​iguales, entonces si a[i] es igual a 1, entonces aumente el valor de A en 1 ; de lo contrario, B en 1.
  • Si A es mayor que B, imprima 1 , de lo contrario imprima 0.

A continuación se muestra la implementación del enfoque anterior.

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to if more number of
// 1's are removed or 0's
void solution(vector<int> a)
{
 
    // Stores count of 1's removes
    int A = 0;
 
    // Stores count of 0's removes
    int B = 0;
 
    // Traverse the array
    for (int i = 1; i < a.size() - 1; i++) {
 
        // Check the divisibility
        if (a[i] == a[i - 1] && a[i] == a[i + 1]) {
 
            // Check for 1 or 0
            if (a[i] == 1)
                A++;
            else
                B++;
        }
    }
 
    // Print the result
    if (A > B)
        cout << ("1");
    else
        cout << ("0");
}
 
// Driver Code
int main()
{
 
    vector<int> a = { 1, 1, 1, 0, 1, 0, 0 };
    solution(a);
    return 0;
}
 
// This code is contributed by lokeshpotta20.

Java

// Java program for above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to if more number of
    // 1's are removed or 0's
    public static void solution(int[] a)
    {
 
        // Stores count of 1's removes
        int A = 0;
 
        // Stores count of 0's removes
        int B = 0;
 
        // Traverse the array
        for (int i = 1; i < a.length - 1; i++) {
 
            // Check the divisibility
            if (a[i] == a[i - 1]
                && a[i] == a[i + 1]) {
 
                // Check for 1 or 0
                if (a[i] == 1)
                    A++;
                else
                    B++;
            }
        }
 
        // Print the result
        if (A > B)
            System.out.println("1 ");
        else
            System.out.println("0 ");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int a[] = { 1, 1, 1, 0, 1, 0, 0 };
        solution(a);
    }
}

Python3

# Python3 program for above approach
 
 
# Function to if more number of
# 1's are removed or 0's
def solution(a) :
 
    # Stores count of 1's removes
    A = 0;
 
    # Stores count of 0's removes
    B = 0;
 
    # Traverse the array
    for i in range(1 , len(a)- 1) :
 
        # Check the divisibility
        if (a[i] == a[i - 1] and a[i] == a[i + 1]) :
 
            # Check for 1 or 0
            if (a[i] == 1) :
                A += 1;
            else :
                B += 1;
 
    # Print the result
    if (A > B) :
        print("1");
    else :
        print("0");
 
# Driver Code
if __name__ == "__main__" :
 
 
    a = [ 1, 1, 1, 0, 1, 0, 0 ];
    solution(a);
 
    # This code is contributed by AnkThon

C#

// C# program for above approach
using System;
public class GFG {
 
    // Function to if more number of
    // 1's are removed or 0's
    public static void solution(int[] a)
    {
 
        // Stores count of 1's removes
        int A = 0;
 
        // Stores count of 0's removes
        int B = 0;
 
        // Traverse the array
        for (int i = 1; i < a.Length - 1; i++) {
 
            // Check the divisibility
            if (a[i] == a[i - 1]
                && a[i] == a[i + 1]) {
 
                // Check for 1 or 0
                if (a[i] == 1)
                    A++;
                else
                    B++;
            }
        }
 
        // Print the result
        if (A > B)
            Console.WriteLine("1 ");
        else
            Console.WriteLine("0 ");
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int []a = { 1, 1, 1, 0, 1, 0, 0 };
        solution(a);
    }
}
 
// This code is contributed by AnkThon

Javascript

<script>
 
 
// Function to if more number of
// 1's are removed or 0's
function solution(a) {
 
  // Stores count of 1's removes
  let A = 0;
 
  // Stores count of 0's removes
  let B = 0;
 
  // Traverse the array
  for (let i = 1; i < a.length - 1; i++) {
 
    // Check the divisibility
    if (a[i] == a[i - 1] && a[i] == a[i + 1]) {
 
      // Check for 1 or 0
      if (a[i] == 1)
        A++;
      else
        B++;
    }
  }
 
  // Print the result
  if (A > B)
    document.write(("1"));
  else
    document.write(("0"));
}
 
// Driver Code
 
 
let a = [1, 1, 1, 0, 1, 0, 0];
solution(a);
 
// This code is contributed by Saurabh Jaiswal.
</script>
Producción

1 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por iramkhalid24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *