Mediana de Bitwise XOR de todas las subarrays a partir de la esquina superior izquierda

Dada una array 2D mat[][] de tamaño N * M , la tarea es encontrar la mediana de Bitwise XOR de todas las subarrays posibles de la array dada que tiene el elemento superior izquierdo en (0, 0) .

Ejemplos:

Entrada: M[][] = { { 1, 2 }, { 2, 3 } } 
Salida: 2.5 
Explicación: 
XOR bit a bit de la subarray cuya esquina superior izquierda es (0, 0) y la esquina inferior derecha es (0, 0) es mat[0][0] = 1. 
XOR bit a bit de la subarray cuya esquina superior izquierda es (0, 0) y la esquina inferior derecha es (0, 1) es mat[0][0] ^ mat[0][1 ] = 3. 
Bitwise XOR de la subarray cuya esquina superior izquierda es (0, 0) y la esquina inferior derecha es (1, 0) es mat[0][0] ^ mat[1][0] = 3. 
Bitwise XOR de subarray cuya esquina superior izquierda es (0, 0) y la esquina inferior derecha es (1, 1) es mat[0][0] ^ mat[1][0] ^ mat[0][1] ^ mat[1] [1] = 2. 
Mediana de XOR bit a bit de todas las subarray posibles cuya esquina superior izquierda es (2 + 3) / 2 = 2,5.

Entrada: M[][] = { { 1, 5, 2 }, { 2, 3, 23 }, { 7, 43, 13 } }
Salida: 5

Enfoque: El problema se puede resolver usando programación dinámica basada en la siguiente relación de recurrencia

dp[i][j] = dp[i – 1][j – 1] ^ dp[i][j – 1] ^ dp[i – 1][j] ^ mat[i][j]

mat[i][j]: almacena el XOR bit a bit de la subarray cuya esquina superior izquierda es (0, 0) y cuya esquina inferior derecha es (i, j).

Siga los pasos a continuación para resolver el problema:

• Inicialice una array , digamos XOR[] , para almacenar el XOR bit a bit de todas las subarrays posibles que tengan la esquina superior izquierda (0, 0) .
• Inicialice una array 2D , digamos dp[][], donde dp[i][j] almacena el XOR bit a bit de la subarray cuya esquina superior izquierda es (0, 0) y la esquina inferior derecha es (i, j) .
• Llene la array dp[][] usando el método de tabulación .
• Almacene todos los elementos de la array dp[][] en XOR[] .
• Finalmente, imprima la mediana de la array XOR[] .

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

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// Function to find the median of bitwise XOR
// of all the submatrix whose topmost leftmost
// corner is (0, 0)
double findMedXOR(int mat[][2], int N, int M)
{
 
    // dp[i][j]: Stores the bitwise XOR of
    // submatrix having top left corner
    // at (0, 0) and bottom right corner at (i, j)
    int dp[N][M];
 
    int med[N * M];
 
    dp[0][0] = mat[0][0];
 
    med[0] = dp[0][0];
 
    // Stores count of submatrix
    int len = 1;
 
    // Base Case
    for (int i = 1; i < N; i++) {
 
        dp[i][0]
            = dp[i - 1][0] ^ mat[i][0];
        med[len++] = dp[i][0];
    }
 
    // Base Case
    for (int i = 1; i < M; i++) {
 
        dp[0][i]
            = dp[0][i - 1] ^ mat[0][i];
 
        med[len++] = dp[0][i];
    }
 
    // Fill dp[][] using tabulation
    for (int i = 1; i < N; i++) {
 
        for (int j = 1; j < M; j++) {
 
            // Fill dp[i][j]
            dp[i][j] = dp[i - 1][j]
                       ^ dp[i][j - 1]
                       ^ dp[i - 1][j - 1]
                       ^ mat[i][j];
 
            med[len++] = dp[i][j];
        }
    }
 
    sort(med, med + len);
 
    if (len % 2 == 0) {
 
        return (med[(len / 2)]
                + med[(len / 2) - 1])
               / 2.0;
    }
 
    return med[len / 2];
}
 
// Driver Code
int main()
{
 
    int mat[][2] = { { 1, 2 }, { 2, 3 } };
 
    int N = sizeof(mat) / sizeof(mat[0]);
    int M = 2;
    cout << findMedXOR(mat, N, M);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
 
  // Function to find the median of bitwise XOR
  // of all the submatrix whose topmost leftmost
  // corner is (0, 0)
  static double findMedXOR(int mat[][], int N, int M)
  {
 
    // dp[i][j]: Stores the bitwise XOR of
    // submatrix having top left corner
    // at (0, 0) and bottom right corner at (i, j)
    int dp[][] = new int[N][M];
    int med[] = new int[N * M];
    dp[0][0] = mat[0][0];
    med[0] = dp[0][0];
 
    // Stores count of submatrix
    int len = 1;
 
    // Base Case
    for (int i = 1; i < N; i++)
    {
      dp[i][0] = dp[i - 1][0] ^ mat[i][0];
      med[len++] = dp[i][0];
    }
 
    // Base Case
    for (int i = 1; i < M; i++)
    {
 
      dp[0][i] = dp[0][i - 1] ^ mat[0][i];
      med[len++] = dp[0][i];
    }
 
    // Fill dp[][] using tabulation
    for (int i = 1; i < N; i++)
    {
      for (int j = 1; j < M; j++)
      {
 
        // Fill dp[i][j]
        dp[i][j] = dp[i - 1][j]
          ^ dp[i][j - 1]
          ^ dp[i - 1][j - 1]
          ^ mat[i][j];
 
        med[len++] = dp[i][j];
      }
    }
    Arrays.sort(med);
    if (len % 2 == 0)
    {
      return (med[(len / 2)]
              + med[(len / 2) - 1])
        / 2.0;
    }
    return med[len / 2];
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int mat[][] = { { 1, 2 }, { 2, 3 } };
    int N = mat.length;
    int M = 2;
    System.out.println(findMedXOR(mat, N, M));
  }
}
 
// This code is contributed by susmitakundugoaldanga

# Python program to implement
# the above approach
 
# Function to find the median of bitwise XOR
# of all the submatrix whose topmost leftmost
# corner is (0, 0)
def findMedXOR(mat, N, M):
   
    # dp[i][j]: Stores the bitwise XOR of
    # submatrix having top left corner
    # at (0, 0) and bottom right corner at (i, j)
    dp = [[0 for i in range(M)] for j in range(N)];
    med = [0] * (N * M);
    dp[0][0] = mat[0][0];
    med[0] = dp[0][0];
 
    # Stores count of submatrix
    len = 1;
 
    # Base Case
    for i in range(1, N):
        dp[i][0] = dp[i - 1][0] ^ mat[i][0];
        med[len] = dp[i][0];
        len += 1;
 
    # Base Case
    for i in range(1, M):
        dp[0][i] = dp[0][i - 1] ^ mat[0][i];
        med[len] = dp[0][i];
        len += 1
 
    # Fill dp using tabulation
    for i in range(1, N):
        for j in range(1, M):
           
            # Fill dp[i][j]
            dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ mat[i][j];
            med[len] = dp[i][j];
            len += 1
 
    med.sort();
    if (len % 2 == 0):
        return (med[(len // 2)] + med[(len // 2) - 1]) / 2.0;
    return med[len // 2];
 
# Driver code
if __name__ == '__main__':
    mat = [[1, 2], [2, 3]];
    N = len(mat[0]);
    M = 2;
    print(findMedXOR(mat, N, M));
 
    # This code is contributed by 29AjayKumar

// C# program to implement
// the above approach
using System;
class GFG
{
 
  // Function to find the median of bitwise XOR
  // of all the submatrix whose topmost leftmost
  // corner is (0, 0)
  static double findMedXOR(int [,]mat, int N, int M)
  {
 
    // dp[i,j]: Stores the bitwise XOR of
    // submatrix having top left corner
    // at (0, 0) and bottom right corner at (i, j)
    int [,]dp = new int[N, M];
    int []med = new int[N * M];
    dp[0, 0] = mat[0, 0];
    med[0] = dp[0, 0];
 
    // Stores count of submatrix
    int len = 1;
 
    // Base Case
    for (int i = 1; i < N; i++)
    {
      dp[i, 0] = dp[i - 1, 0] ^ mat[i, 0];
      med[len++] = dp[i, 0];
    }
 
    // Base Case
    for (int i = 1; i < M; i++)
    {
 
      dp[0, i] = dp[0, i - 1] ^ mat[0, i];
      med[len++] = dp[0, i];
    }
 
    // Fill [,]dp using tabulation
    for (int i = 1; i < N; i++)
    {
      for (int j = 1; j < M; j++)
      {
 
        // Fill dp[i,j]
        dp[i, j] = dp[i - 1, j]
          ^ dp[i, j - 1]
          ^ dp[i - 1, j - 1]
          ^ mat[i, j];
 
        med[len++] = dp[i, j];
      }
    }
    Array.Sort(med);
    if (len % 2 == 0)
    {
      return (med[(len / 2)]
              + med[(len / 2) - 1])
        / 2.0;
    }
    return med[len / 2];
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int [,]mat = { { 1, 2 }, { 2, 3 } };
    int N = mat.GetLength(0);
    int M = 2;
    Console.WriteLine(findMedXOR(mat, N, M));
  }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find the median of bitwise XOR
// of all the submatrix whose topmost leftmost
// corner is (0, 0)
function findMedXOR(mat, N, M)
{
 
    // dp[i][j]: Stores the bitwise XOR of
    // submatrix having top left corner
    // at (0, 0) and bottom right corner at (i, j)
    let dp = new Array(N);
    for (let i = 0; i < N; i++)
        dp[i] = new Array(M);
 
    let med = new Array(N * M);
 
    dp[0][0] = mat[0][0];
 
    med[0] = dp[0][0];
 
    // Stores count of submatrix
    let len = 1;
 
    // Base Case
    for (let i = 1; i < N; i++) {
 
        dp[i][0]
            = dp[i - 1][0] ^ mat[i][0];
        med[len++] = dp[i][0];
    }
 
    // Base Case
    for (let i = 1; i < M; i++) {
 
        dp[0][i]
            = dp[0][i - 1] ^ mat[0][i];
 
        med[len++] = dp[0][i];
    }
 
    // Fill dp[][] using tabulation
    for (let i = 1; i < N; i++) {
 
        for (let j = 1; j < M; j++) {
 
            // Fill dp[i][j]
            dp[i][j] = dp[i - 1][j]
                       ^ dp[i][j - 1]
                       ^ dp[i - 1][j - 1]
                       ^ mat[i][j];
 
            med[len++] = dp[i][j];
        }
    }
 
    med.sort();
 
    if (len % 2 == 0) {
 
        return (med[parseInt(len / 2)]
                + med[parseInt(len / 2) - 1])
               / 2.0;
    }
 
    return med[parseInt(len / 2)];
}
 
// Driver Code
 
    let mat = [ [ 1, 2 ], [ 2, 3 ] ];
 
    let N = mat.length;
    let M = 2;
    document.write(findMedXOR(mat, N, M));
 
</script>

2.5

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