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