Dada una array arr[] con N elementos, la tarea es encontrar si todos los elementos de la array dada pueden convertirse en 0 mediante operaciones dadas. Solo se pueden realizar 2 tipos de operaciones en esta array:
- Divida un elemento B en 2 elementos C y D tales que B = C+ D.
- Combinar 2 elementos P y Q como un elemento R tal que R = P^Q es decir (XOR de P y Q).
¿Tiene que determinar si es posible convertir la array A al tamaño 1, que contiene un solo elemento igual a 0 después de varias divisiones y/o fusiones?
Ejemplos:
Entrada: arr = [9, 17]
Salida: Sí
Explicación: La siguiente es una posible secuencia de operaciones:
1) Combinar, es decir, 9 XOR 17 = 24
2) Dividir 24 en dos partes, cada una de tamaño 12
3) Combinar, es decir, 12 XOR 12 = 0
Como solo hay 1 elemento, es decir, 0. Entonces es posible.Entrada: arr = [1]
Salida: No
Explicación: No hay forma posible de convertirlo en 0.
Acercarse :
- Si cualquier elemento en la array es par, entonces puede convertirse en 0. Dividir ese elemento en dos partes iguales de arr[i]/2 y arr[i]/2. XOR de dos números iguales es cero. Por lo tanto esta estrategia hace un elemento 0.
- Si algún elemento es impar. Divídelo en dos partes: 1 y arr[i]-1. Dado que arr[i]-1 es par, puede convertirse en 0 mediante la estrategia anterior. Por lo tanto, un elemento impar puede reducir su tamaño a 1. Por lo tanto, dos elementos impares pueden convertirse en 0 siguiendo la estrategia anterior y finalmente XOR (es decir, 1) como 1 XOR 1 = 0. Por lo tanto, si el número de elementos impares en el array es par, entonces la respuesta es posible. De lo contrario, quedará un elemento de valor 1 y no es posible satisfacer la condición.
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 that finds if it is
// possible to make the array
// contain only 1 element i.e. 0
string solve(vector<int>& A)
{
int i, ctr = 0;
for (i = 0; i < A.size();
i++) {
// Check if element is odd
if (A[i] % 2) {
ctr++;
}
}
// According to the logic
// in above approach
if (ctr % 2) {
return "No";
}
else {
return "Yes";
}
}
// Driver code
int main()
{
vector<int> arr = { 9, 17 };
cout << solve(arr) << endl;
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function that finds if it is
// possible to make the array
// contain only 1 element i.e. 0
public static String solve(int[] A)
{
int i, ctr = 0;
for(i = 0; i < A.length; i++)
{
// Check if element is odd
if (A[i] % 2 == 1)
{
ctr++;
}
}
// According to the logic
// in above approach
if (ctr % 2 == 1)
{
return "No";
}
else
{
return "Yes";
}
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 9, 17 };
System.out.println(solve(arr));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach # Function that finds if it is # possible to make the array # contain only 1 element i.e. 0 def solve(A): ctr = 0 for i in range(len(A)): # Check if element is odd if A[i] % 2 == 1: ctr += 1 # According to the logic # in above approach if ctr % 2 == 1: return 'No' else : return 'Yes' # Driver code if __name__=='__main__': arr = [9, 17] print(solve(arr)) # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
class GFG{
// Function that finds if it is
// possible to make the array
// contain only 1 element i.e. 0
public static string solve(int[] A)
{
int i, ctr = 0;
for(i = 0; i < A.Length; i++)
{
// Check if element is odd
if (A[i] % 2 == 1)
{
ctr++;
}
}
// According to the logic
// in above approach
if (ctr % 2 == 1)
{
return "No";
}
else
{
return "Yes";
}
}
// Driver code
public static void Main()
{
int[] arr = { 9, 17 };
Console.Write(solve(arr));
}
}
// This code is contributed by chitranayal
Javascript
<script>
// Javascript program for the above approach
// Function that finds if it is
// possible to make the array
// contain only 1 element i.e. 0
function solve(A)
{
let i, ctr = 0;
for (i = 0; i < A.length;
i++) {
// Check if element is odd
if (A[i] % 2) {
ctr++;
}
}
// According to the logic
// in above approach
if (ctr % 2) {
return "No";
}
else {
return "Yes";
}
}
// Driver code
let arr = [ 9, 17 ];
document.write(solve(arr));
</script>
Yes
Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)
Otro enfoque:
El enfoque es bastante simple, solo tenemos que encontrar el XOR de los elementos de la array y, si es impar, entonces dividirlo será útil, ya que cada vez que el valor de XOR siempre será impar, y si es par tenemos nuestra respuesta, es decir, 0.
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
int[] A = { 9, 17 };
// length of the array
int n = A.length;
// variable to store the value of XOR
int xor = 0;
// traversing the array
for (int i = 0; i < n; i++) {
xor ^= A[i];
}
// checking if the value of XOR is even or odd
// if even printing YES else ONO
if (xor % 2 == 0) {
System.out.print("Yes");
}
else {
System.out.print("No");
}
}
}
Python3
# Python3 program for the above approach # Function that finds if it is # possible to make the array # contain only 1 element i.e. 0 def solve(A): n = len(A) xor = 0 for i in range(n): xor ^= A[i] if(xor % 2 == 0): return "YES" else: return "NO" # Driver code if __name__ == '__main__': arr = [9, 17] print(solve(arr))
Yes
Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)