Compruebe si las filas de una Array se pueden reorganizar para hacer Bitwise XOR de la primera columna distinta de cero

Dada una array mat[][] de tamaño N * M , la tarea es verificar si es posible reorganizar los elementos de la fila de la array de manera que Bitwise XOR del primer elemento de la columna no sea cero. Si es posible, escriba «Sí» , de lo contrario, escriba «No» .

Ejemplos:

Entrada: mat[][] = {{1, 1, 2}, {2, 2, 2}, {3, 3, 3}}
Salida: Sí
Explicación:
Después de reorganizar la primera fila como 2, 1, 1.
Bitwise XOR de la primera columna será 3, es decir, (2 ^ 2 ^ 3).

Entrada: mat[][] = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}}
Salida: No
Explicación:
Como todos los reordenamientos dan el mismo primer elemento, la única combinación es (1 ^ 2 ^ 3) que es igual a cero.
Por lo tanto, no es posible obtener un XOR bit a bit distinto de cero de la primera columna.

Enfoque: siga los pasos a continuación para resolver el problema:

• Encuentra el Bitwise XOR de los elementos de la primera columna de la array y guárdalo en una variable res .
• Si res es distinto de cero, imprima «Sí» .
• De lo contrario, itere sobre todas las filas y encuentre el elemento en una fila que no sea igual al elemento en el primer índice de esta fila.
• Si tal elemento no está presente en ninguna fila en el paso anterior, imprima «No» , de lo contrario, imprima «Sí».

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if there is any
// row where number of unique elements
// are greater than 1
string checkRearrangements(
    vector<vector<int> > mat, int N, int M)
{
    // Iterate over the matrix
    for (int i = 0; i < N; i++) {
 
        for (int j = 1; j < M; j++) {
 
            if (mat[i][0] != mat[i][j]) {
 
                return "Yes";
            }
        }
    }
    return "No";
}
 
// Function to check if it is possible
// to rearrange mat[][] such that XOR
// of its first column is non-zero
string nonZeroXor(vector<vector<int> > mat,
                  int N, int M)
{
    int res = 0;
 
    // Find bitwise XOR of the first
    // column of mat[][]
    for (int i = 0; i < N; i++) {
 
        res = res ^ mat[i][0];
    }
 
    // If bitwise XOR of the first
    // column of mat[][] is non-zero
    if (res != 0)
        return "Yes";
 
    // Otherwise check rearrangements
    else
        return checkRearrangements(mat, N, M);
}
 
// Driver Code
int main()
{
    // Given Matrix mat[][]
    vector<vector<int> > mat
        = { { 1, 1, 2 },
            { 2, 2, 2 },
            { 3, 3, 3 } };
 
    int N = mat.size();
    int M = mat[0].size();
 
    // Function Call
    cout << nonZeroXor(mat, N, M);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
// Function to check if there is any
// row where number of unique elements
// are greater than 1
static String checkRearrangements(int[][] mat,
                                  int N, int M)
{
  // Iterate over the matrix
  for (int i = 0; i < N; i++)
  {
    for (int j = 1; j < M; j++)
    {
      if (mat[i][0] != mat[i][j])
      {
        return "Yes";
      }
    }
  }
  return "No";
}
 
// Function to check if it is possible
// to rearrange mat[][] such that XOR
// of its first column is non-zero
static String nonZeroXor(int[][] mat,
                         int N, int M)
{
  int res = 0;
 
  // Find bitwise XOR of the
  // first column of mat[][]
  for (int i = 0; i < N; i++)
  {
    res = res ^ mat[i][0];
  }
 
  // If bitwise XOR of the first
  // column of mat[][] is non-zero
  if (res != 0)
    return "Yes";
 
  // Otherwise check
  // rearrangements
  else
    return checkRearrangements(mat,
                               N, M);
}
 
// Driver Code
public static void main(String[] args)
{
  // Given Matrix mat[][]
  int[][] mat = {{1, 1, 2},
                 {2, 2, 2},
                 {3, 3, 3}};
 
  int N = mat.length;
  int M = mat[0].length;
 
  // Function Call
  System.out.print(nonZeroXor(mat,
                              N, M));
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
 
# Function to check if there is any
# row where number of unique elements
# are greater than 1
def checkRearrangements(mat, N, M):
     
    # Iterate over the matrix
    for i in range(N):
        for j in range(1, M):
            if (mat[i][0] != mat[i][j]):
                return "Yes"
                 
    return "No"
 
# Function to check if it is possible
# to rearrange mat[][] such that XOR
# of its first column is non-zero
def nonZeroXor(mat, N, M):
 
    res = 0
 
    # Find bitwise XOR of the first
    # column of mat[][]
    for i in range(N):
        res = res ^ mat[i][0]
 
    # If bitwise XOR of the first
    # column of mat[][] is non-zero
    if (res != 0):
        return "Yes"
 
    # Otherwise check rearrangements
    else:
        return checkRearrangements(mat, N, M)
 
# Driver Code
if __name__ == "__main__":
 
    # Given Matrix mat[][]
    mat = [ [ 1, 1, 2 ],
            [ 2, 2, 2 ],
            [ 3, 3, 3 ] ]
 
    N = len(mat)
    M = len(mat[0])
 
    # Function Call
    print(nonZeroXor(mat, N, M))
 
# This code is contributed by chitranayal

// C# program for the
// above approach
using System;
 
class GFG{
 
// Function to check if there is any
// row where number of unique elements
// are greater than 1
static String checkRearrangements(int[,] mat,
                                  int N, int M)
{
   
  // Iterate over the matrix
  for(int i = 0; i < N; i++)
  {
    for(int j = 1; j < M; j++)
    {
      if (mat[i, 0] != mat[i, j])
      {
        return "Yes";
      }
    }
  }
  return "No";
}
 
// Function to check if it is possible
// to rearrange [,]mat such that XOR
// of its first column is non-zero
static String nonZeroXor(int[,] mat,
                         int N, int M)
{
  int res = 0;
 
  // Find bitwise XOR of the
  // first column of [,]mat
  for(int i = 0; i < N; i++)
  {
    res = res ^ mat[i, 0];
  }
 
  // If bitwise XOR of the first
  // column of [,]mat is non-zero
  if (res != 0)
    return "Yes";
 
  // Otherwise check
  // rearrangements
  else
    return checkRearrangements(mat,
                               N, M);
}
 
// Driver Code
public static void Main(String[] args)
{
   
  // Given Matrix [,]mat
  int[,] mat = { { 1, 1, 2 },
                 { 2, 2, 2 },
                 { 3, 3, 3 } };
 
  int N = mat.GetLength(0);
  int M = mat.GetLength(1);
 
  // Function Call
  Console.Write(nonZeroXor(mat,
                           N, M));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to check if there is any
// row where number of unique elements
// are greater than 1
function checkRearrangements(mat, N, M)
{
  // Iterate over the matrix
  for (let i = 0; i < N; i++)
  {
    for (let j = 1; j < M; j++)
    {
      if (mat[i][0] != mat[i][j])
      {
        return "Yes";
      }
    }
  }
  return "No";
}
  
// Function to check if it is possible
// to rearrange mat[][] such that XOR
// of its first column is non-zero
function nonZeroXor(mat, N, M)
{
  let res = 0;
  
  // Find bitwise XOR of the
  // first column of mat[][]
  for (let i = 0; i < N; i++)
  {
    res = res ^ mat[i][0];
  }
  
  // If bitwise XOR of the first
  // column of mat[][] is non-zero
  if (res != 0)
    return "Yes";
  
  // Otherwise check
  // rearrangements
  else
    return checkRearrangements(mat,
                               N, M);
}
 
// Driver Code
 
    // Given Matrix mat[][]
  let mat = [[1, 1, 2],
             [2, 2, 2],
             [3, 3, 3]];
  
  let N = mat.length;
  let M = mat[0].length;
  
  // Function Call
  document.write(nonZeroXor(mat,
                              N, M));
           
</script>

Yes

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)