Dada una array m[][] de dimensiones N × M y un número entero K , calcule XOR(i, j) que es igual a Bitwise Xor de todos los elementos de la subarray desde los índices (1, 1) hasta (i, j) ) , para cada índice de la array. La tarea es encontrar la subarray {(1, 1), …, (i, j)} que tenga el valor K -ésimo XOR(i, j) máximo . Si existen varias subarrays de este tipo, imprima la más pequeña.
Nota: Considere el índice inicial de la array de (1, 1).
Ejemplos:
Entrada: m[][] = {{1, 2}, {2, 3}}, K = 2
Salida: 1 2
Explicación:
XOR(1, 1) : m[1][1] = 1
XOR(1 , 2): m[1][1] xor m[1][2] = 3
XOR(2, 1): m[1][1] xor m[2][1] = 3
XOR(2, 2 ): m[1][1] xor m[1][2] xor m[2][1] xor m[2][2] = 2
Por lo tanto, el segundo valor máximo es 3 en la posición [1, 2] .Entrada: m[][] = {{1, 2, 3}, {2, 2, 1}, {2, 4, 2} }, k = 1
Salida: 3 2
Enfoque: La idea es encontrar XOR (i, j) usando Programación Dinámica .
- Calcule el bit a bit XOR(i, j) como xor[i][j] = xor[i-1][j] ^ xor[i][j-1] ^ xor[i-1][j-1] ^ m[i][j].
- Almacene los valores XOR(i, j) obtenidos para los respectivos índices (i, j) en un Map .
- Encuentre el K -ésimo máximo de todos los valores XOR(i, j) usando un Min-heap de tamaño K.
- Encuentre el índice más pequeño (i, j) para el cual XOR(i, j) es igual al K -ésimo máximo obtenido en el paso anterior usando Map .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print smallest index of
// Kth maximum xors value of submatrices
void smallestPosition(int m[][3], int k, int row)
{
// Dimensions of matrix
int n = row;
int mm = row;
// Stores xors values for every index
int xors[n][mm];
// Min heap to find the
// kth maximum xors value
priority_queue<int, vector<int>,
greater<int>> minHeap;
// Stores indices for
// corresponding xors values
map<int, vector<int>> map;
// Traversing matrix to
// calculate xors values
for(int i = 0; i < n; i++)
{
for(int j = 0; j < mm; j++)
{
int a = i - 1 >= 0 ? xors[i - 1][j] : 0;
int b = j - 1 >= 0 ? xors[i][j - 1] : 0;
int c = (i - 1 >= 0 && j - 1 >= 0) ?
xors[i - 1][j - 1] : 0;
xors[i][j] = m[i][j] ^ a ^ b ^ c;
// Insert calculated value
// in Min Heap
minHeap.push(xors[i][j]);
// If size exceeds k
if (minHeap.size() > k)
{
// Remove the minimum
minHeap.pop();
}
// Store smallest index
// containing xors[i][j]
if (map.find(xors[i][j]) == map.end())
map[xors[i][j]] = {i, j};
}
}
// Stores the kth maximum element
int kth_max_e = minHeap.top();
// Print the required index
cout << (map[kth_max_e][0] + 1) << " "
<< (map[kth_max_e][1] + 1);
}
// Driver Code
int main()
{
int m[][3] = { { 1, 2, 3 },
{ 2, 2, 1 },
{ 2, 4, 2 } };
int k = 1;
// Function call
smallestPosition(m, k, 3);
}
// This code is contributed by grand_master
Java
// Java Program for above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to print smallest index of
// Kth maximum Xor value of submatrices
static void smallestPosition(int m[][], int k)
{
// Dimensions of matrix
int n = m.length;
int mm = m[0].length;
// Stores XOR values for every index
int[][] xor = new int[n][mm];
// Min heap to find the
// kth maximum XOR value
PriorityQueue<Integer> minHeap
= new PriorityQueue<>();
// Stores indices for
// corresponding XOR values
Map<Integer, int[]> map
= new HashMap<>();
// Traversing matrix to
// calculate XOR values
for (int i = 0; i < n; i++) {
for (int j = 0; j < mm; j++) {
int a = i - 1 >= 0
? xor[i - 1][j]
: 0;
int b = j - 1 >= 0
? xor[i][j - 1]
: 0;
int c = (i - 1 >= 0 && j - 1 >= 0)
? xor[i - 1][j - 1]
: 0;
xor[i][j] = m[i][j] ^ a ^ b ^ c;
// Insert calculated value
// in Min Heap
minHeap.add(xor[i][j]);
// If size exceeds k
if (minHeap.size() > k) {
// Remove the minimum
minHeap.poll();
}
// Store smallest index
// containing xor[i][j]
if (!map.containsKey(xor[i][j]))
map.put(xor[i][j],
new int[] { i, j });
}
}
// Stores the kth maximum element
int kth_max_e = minHeap.poll();
// Print the required index
System.out.println(
(map.get(kth_max_e)[0] + 1)
+ " " + (map.get(kth_max_e)[1] + 1));
}
// Driver Code
public static void main(String[] args)
{
int m[][] = { { 1, 2, 3 },
{ 2, 2, 1 },
{ 2, 4, 2 } };
int k = 1;
// Function call
smallestPosition(m, k);
}
}
Python3
# Python3 Program for the
# above approach
# Function to print smallest index of
# Kth maximum Xor value of submatrices
def smallestPosition(m, k) :
# Dimensions of matrix
n = len(m)
mm = len(m[1])
# Stores XOR values for
# every index
xor = [[0 for i in range(mm)] for j in range(n)]
# Min heap to find the
# kth maximum XOR value
minHeap = []
# Stores indices for
# corresponding XOR values
Map = {}
# Traversing matrix to
# calculate XOR values
for i in range(n) :
for j in range(mm) :
if i - 1 >= 0 :
a = xor[i - 1][j]
else :
a = 0
if j - 1 >= 0 :
b = xor[i][j - 1]
else :
b = 0
if i - 1 >= 0 and j - 1 >= 0 :
c = xor[i - 1][j - 1]
else :
c = 0
xor[i][j] = m[i][j] ^ a ^ b ^ c
# Insert calculated value
# in Min Heap
minHeap.append(xor[i][j])
minHeap.sort()
# If size exceeds k
if (len(minHeap) > k) :
# Remove the minimum
del minHeap[0]
# Store smallest index
# containing xor[i,j]
if xor[i][j] not in Map :
Map[xor[i][j]] = [i, j]
minHeap.sort()
# Stores the kth maximum
# element
kth_max_e = minHeap[0]
# Print the required index
print((Map[kth_max_e][0] + 1), (Map[kth_max_e][1] + 1))
# Driver code
m = [[1, 2, 3],
[2, 2, 1],
[2, 4, 2]]
k = 1
# Function call
smallestPosition(m, k)
# This code is contributed by divyesh072019
C#
// C# Program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print smallest index of
// Kth maximum Xor value of submatrices
static void smallestPosition(int [,]m,
int k)
{
// Dimensions of matrix
int n = m.GetLength(0);
int mm = m.GetLength(1);
// Stores XOR values for
// every index
int[,] xor = new int[n, mm];
// Min heap to find the
// kth maximum XOR value
List<int> minHeap =
new List<int>();
// Stores indices for
// corresponding XOR values
Dictionary<int,
int[]> map = new Dictionary<int,
int[]>();
// Traversing matrix to
// calculate XOR values
for (int i = 0; i < n; i++)
{
for (int j = 0; j < mm; j++)
{
int a = i - 1 >= 0 ?
xor[i - 1, j] : 0;
int b = j - 1 >= 0 ?
xor[i, j - 1] : 0;
int c = (i - 1 >= 0 &&
j - 1 >= 0) ?
xor[i - 1, j - 1] : 0;
xor[i, j] = m[i, j] ^
a ^ b ^ c;
// Insert calculated value
// in Min Heap
minHeap.Add(xor[i, j]);
minHeap.Sort();
// If size exceeds k
if (minHeap.Count > k)
{
// Remove the minimum
minHeap.RemoveAt(0);
}
// Store smallest index
// containing xor[i,j]
if (!map.ContainsKey(xor[i, j]))
map.Add(xor[i, j],
new int[] {i, j});
}
}
minHeap.Sort();
// Stores the kth maximum
// element
int kth_max_e = minHeap[0];
// Print the required index
Console.WriteLine((map[kth_max_e][0] + 1) +
" " + (map[kth_max_e][1] + 1));
}
// Driver Code
public static void Main(String[] args)
{
int [,]m = {{1, 2, 3},
{2, 2, 1},
{2, 4, 2}};
int k = 1;
// Function call
smallestPosition(m, k);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript Program for the
// above approach
// Function to print smallest index of
// Kth maximum Xor value of submatrices
function smallestPosition(m, k){
// Dimensions of matrix
let n = m.length
let mm = m[1].length
// Stores XOR values for
// every index
let xor = new Array(n).fill(0).map(()=>new Array(mm).fill(0))
// Min heap to find the
// kth maximum XOR value
let minHeap = []
// Stores indices for
// corresponding XOR values
let Map1 = new Map()
let a = 0,b = 0,c = 0
// Traversing matrix to
// calculate XOR values
for(let i=0;i<n;i++){
for(let j=0;j<mm;j++){
if(i - 1 >= 0)
a = xor[i - 1][j]
else
a = 0
if(j - 1 >= 0)
b = xor[i][j - 1]
else
b = 0
if(i - 1 >= 0 && j - 1 >= 0)
c = xor[i - 1][j - 1]
else
c = 0
xor[i][j] = m[i][j] ^ a ^ b ^ c
// Insert calculated value
// in Min Heap
minHeap.push(xor[i][j])
minHeap.sort()
// If size exceeds k
if (minHeap.length > k){
// Remove the minimum
minHeap.shift()
}
// Store smallest index
// containing xor[i,j]
if(!Map1.has(xor[i][j]))
Map1.set(xor[i][j],[i, j])
}
}
minHeap.sort()
// Stores the kth maximum
// element
let kth_max_e = minHeap[0]
// Print the required index
document.write((Map1.get(kth_max_e)[0] + 1), (Map1.get(kth_max_e)[1] + 1),"</br>")
}
// Driver code
let m = [[1, 2, 3],
[2, 2, 1],
[2, 4, 2]]
let k = 1
// Function call
smallestPosition(m, k)
// This code is contributed by shinjanpatra
</script>
Producción:
3 2
Complejidad de Tiempo: O(N * M * log K)
Espacio Auxiliar: O(N * M)