Dada una array ‘N*N’ , la tarea es encontrar el XOR de los XOR de todas las subarrays posibles.
Ejemplos:
Input :arr = {{3, 1},
{1, 3}}
Output : 0
Explanation: All the elements lie in 4 submatrices each.
4 being even, there total contribution towards
final answer becomes 0. Thus, ans = 0.
Input : arr = {{6, 7, 13},
{8, 3, 4},
{9, 7, 6}};
Output : 4
Un enfoque simple es generar todas las subarrays posibles, encontrar el XOR de cada subarray de forma única y luego XOR en todas ellas. La complejidad temporal de este enfoque será O(n 6 ).
Mejor solución: para cada índice (R, C), intentaremos encontrar el número de subarrays en las que se encuentra ese índice. Si el número de subarrays es impar, la respuesta final se actualizará como ans = (ans ^ arr[R][C]) . En caso de par, no necesitamos actualizar la respuesta. Esto funciona porque un número XOR consigo mismo da cero y el orden de operación no afecta el valor XOR final.
Suponiendo una indexación basada en 0, el número de subarrays de un índice (R, C) es igual a
(R + 1)*(C + 1)*(N - R)*(N - C)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the XOR of XOR's of
// all submatrices
#include <iostream>
using namespace std;
#define n 3
// Function to find to required
// XOR value
int submatrixXor(int arr[][n])
{
int ans = 0;
// Nested loop to find the
// number of sub-matrix each
// index belongs to
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
if ((top_left % 2 == 1) && (bottom_right % 2 == 1))
ans = (ans ^ arr[i][j]);
}
}
return ans;
}
// Driver Code
int main()
{
int arr[][n] = { { 6, 7, 13 },
{ 8, 3, 4 },
{ 9, 7, 6 } };
cout << submatrixXor(arr);
return 0;
}
Java
//Java program to find the XOR of XOR's
// of all submatrices
class GFG
{
// Function to find to required
// XOR value
static int submatrixXor(int[][]arr)
{
int n = 3;
int ans = 0;
// Nested loop to find the
// number of sub-matrix each
// index belongs to
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
if ((top_left % 2 == 1) &&
(bottom_right % 2 == 1))
ans = (ans ^ arr[i][j]);
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[][] arr = {{ 6, 7, 13},
{ 8, 3, 4 },
{ 9, 7, 6 }};
System.out.println(submatrixXor(arr));
}
}
// This code is contributed
// by Code_Mech.
Python3
# Python3 program to find the XOR of # XOR's of all submatrices # Function to find to required # XOR value def submatrixXor(arr, n): ans = 0 # Nested loop to find the # number of sub-matrix each # index belongs to for i in range(0, n): for j in range(0, n): # Number of ways to choose # from top-left elements top_left = (i + 1) * (j + 1) # Number of ways to choose # from bottom-right elements bottom_right = (n - i) * (n - j) if (top_left % 2 == 1 and bottom_right % 2 == 1): ans = (ans ^ arr[i][j]) return ans # Driver code n = 3 arr = [[6, 7, 13], [8, 3, 4], [9, 7, 6]] print(submatrixXor(arr, n)) # This code is contributed by Shrikant13
C#
// C# program to find the XOR of XOR's
// of all submatrices
using System;
class GFG
{
// Function to find to required
// XOR value
static int submatrixXor(int [,]arr)
{
int n = 3;
int ans = 0;
// Nested loop to find the
// number of sub-matrix each
// index belongs to
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
if ((top_left % 2 == 1) &&
(bottom_right % 2 == 1))
ans = (ans ^ arr[i, j]);
}
}
return ans;
}
// Driver Code
public static void Main()
{
int [, ]arr = {{ 6, 7, 13},
{ 8, 3, 4 },
{ 9, 7, 6 }};
Console.Write(submatrixXor(arr));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program to find the XOR of
// XOR's of all submatrices
// Function to find to required
// XOR value
function submatrixXor($arr)
{
$ans = 0;
$n = 3 ;
// Nested loop to find the
// number of sub-matrix each
// index belongs to
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
{
// Number of ways to choose
// from top-left elements
$top_left = ($i + 1) * ($j + 1);
// Number of ways to choose
// from bottom-right elements
$bottom_right = ($n - $i) * ($n - $j);
if (($top_left % 2 == 1) &&
($bottom_right % 2 == 1))
$ans = ($ans ^ $arr[$i][$j]);
}
}
return $ans;
}
// Driver Code
$arr = array(array( 6, 7, 13 ),
array( 8, 3, 4 ),
array( 9, 7, 6 ));
echo submatrixXor($arr);
# This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program to find the
// XOR of XOR's of
// all submatrices
const n = 3;
// Function to find to required
// XOR value
function submatrixXor(arr)
{
let ans = 0;
// Nested loop to find the
// number of sub-matrix each
// index belongs to
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// Number of ways to choose
// from top-left elements
let top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
let bottom_right = (n - i) * (n - j);
if ((top_left % 2 == 1) &&
(bottom_right % 2 == 1))
ans = (ans ^ arr[i][j]);
}
}
return ans;
}
// Driver Code
let arr = [ [ 6, 7, 13 ],
[ 8, 3, 4 ],
[ 9, 7, 6 ] ];
document.write(submatrixXor(arr));
</script>
Producción:
4
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA