Dada una array 2-D de elementos de array de orden NXM , la tarea es verificar si podemos seleccionar un número de cada fila de tal manera que xor de los números seleccionados sea mayor que 0 .
Nota : Hay un mínimo de 2 filas.
Ejemplos:
Input: a[][] = {{7, 7, 7},
{10, 10, 7}}
Output: Yes
Input: a[][] = {{1, 1, 1},
{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}
Output: No
Enfoque : inicialmente verifique si xor de los elementos de la primera columna de cada fila es 0 o no. Si es distinto de cero, entonces es posible. Si es cero, compruebe si alguna de las filas tiene dos o más elementos distintos, entonces también es posible. Si no se cumplen las dos condiciones anteriores, entonces no es posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define N 2
#define M 3
// Function to check if a number from every row
// can be selected such that xor of the numbers
// is greater than zero
bool check(int mat[N][M])
{
int xorr = 0;
// Find the xor of first
// column for every row
for (int i = 0; i < N; i++) {
xorr ^= mat[i][0];
}
// If Xorr is 0
if (xorr != 0)
return true;
// Traverse in the matrix
for (int i = 0; i < N; i++) {
for (int j = 1; j < M; j++) {
// Check is atleast
// 2 distinct elements
if (mat[i][j] != mat[i][0])
return true;
}
}
return false;
}
// Driver code
int main()
{
int mat[N][M] = { { 7, 7, 7 },
{ 10, 10, 7 } };
if (check(mat))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG
{
static int N = 2;
static int M = 3;
// Function to check if a number
// from every row can be selected
// such that xor of the numbers
// is greater than zero
static boolean check(int mat[][])
{
int xorr = 0;
// Find the xor of first
// column for every row
for (int i = 0; i < N; i++)
{
xorr ^= mat[i] [0];
}
// If Xorr is 0
if (xorr != 0)
return true;
// Traverse in the matrix
for (int i = 0; i < N; i++)
{
for (int j = 1; j < M; j++)
{
// Check is atleast
// 2 distinct elements
if (mat[i] [j] != mat[i] [0])
return true;
}
}
return false;
}
// Driver code
public static void main (String[] args)
{
int mat[][] = {{ 7, 7, 7 },
{ 10, 10, 7 }};
if (check(mat))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by ajit
Python3
# Python3 program to implement
# the above approach
N = 2
M = 3
# Function to check if a number from every row
# can be selected such that xor of the numbers
# is greater than zero
def check(mat):
xorr = 0
# Find the xor of first
# column for every row
for i in range(N):
xorr ^= mat[i][0]
# If Xorr is 0
if (xorr != 0):
return True
# Traverse in the matrix
for i in range(N):
for j in range(1, M):
# Check is atleast
# 2 distinct elements
if (mat[i][j] != mat[i][0]):
return True
return False
# Driver code
mat = [[ 7, 7, 7 ],
[ 10, 10, 7 ]]
if (check(mat)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar
C#
// C# program to implement
// the above approach
using System;
class GFG
{
static int N = 2;
static int M = 3;
// Function to check if a number
// from every row can be selected
// such that xor of the numbers
// is greater than zero
static bool check(int [,]mat)
{
int xorr = 0;
// Find the xor of first
// column for every row
for (int i = 0; i < N; i++)
{
xorr ^= mat[i, 0];
}
// If Xorr is 0
if (xorr != 0)
return true;
// Traverse in the matrix
for (int i = 0; i < N; i++)
{
for (int j = 1; j < M; j++)
{
// Check is atleast
// 2 distinct elements
if (mat[i, j] != mat[i, 0])
return true;
}
}
return false;
}
// Driver code
static void Main()
{
int [,]mat = {{ 7, 7, 7 },
{ 10, 10, 7 }};
if (check(mat))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to implement
// the above approach
$N = 2;
$M = 3;
// Function to check if a number from every row
// can be selected such that xor of the numbers
// is greater than zero
function check($mat)
{
global $N ;
global $M ;
$xorr = 0;
// Find the xor of first
// column for every row
for ($i = 0; $i < $N; $i++)
{
$xorr = $xorr ^ $mat[$i][0];
}
// If Xorr is 0
if ($xorr != 0)
return true;
// Traverse in the matrix
for ($i = 0; $i < $N; $i++)
{
for ( $j = 1; $j < $M; $j++)
{
// Check is atleast
// 2 distinct elements
if ($mat[$i][$j] != $mat[$i][0])
return true;
}
}
return false;
}
// Driver code
$mat = array(array( 7, 7, 7 ),
array( 10, 10, 7 ));
if (check($mat))
echo "Yes";
else
echo "No";
// This code is contributed by Tushil..
?>
Javascript
<script>
// Javascript program to implement
// the above approach
let N = 2;
let M = 3;
// Function to check if a number from every row
// can be selected such that xor of the numbers
// is greater than zero
function check(mat)
{
let xorr = 0;
// Find the xor of first
// column for every row
for (let i = 0; i < N; i++) {
xorr ^= mat[i][0];
}
// If Xorr is 0
if (xorr != 0)
return true;
// Traverse in the matrix
for (let i = 0; i < N; i++) {
for (let j = 1; j < M; j++) {
// Check is atleast
// 2 distinct elements
if (mat[i][j] != mat[i][0])
return true;
}
}
return false;
}
// Driver code
let mat = [ [ 7, 7, 7 ],
[ 10, 10, 7 ] ];
if (check(mat))
document.write("Yes");
else
document.write("No");
// This code is contributed by souravmahato348.
</script>
Producción:
Yes
Complejidad de tiempo: O(N * M)
Espacio Auxiliar: O(1)