Smallest submatrix with Kth maximum XOR | C ++ program for above approach ; Function to print smallest index of Kth maximum xors value of submatrices ; Dimensions of matrix ; Stores xors values for every index ; Min heap to find the kth maximum xors value ; Stores indices for corresponding xors values ; Traversing matrix to calculate xors values ; Insert calculated value in Min Heap ; If size exceeds k ; Remove the minimum ; Store smallest index containing xors [ i ] [ j ] ; Stores the kth maximum element ; Print the required index ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void smallestPosition ( int m [ ] [ 3 ] , int k , int row ) { int n = row ; int mm = row ; int xors [ n ] [ mm ] ; priority_queue < int , vector < int > , greater < int > > minHeap ; map < int , vector < int > > map ; 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 ; minHeap . push ( xors [ i ] [ j ] ) ; if ( minHeap . size ( ) > k ) { minHeap . pop ( ) ; } if ( map . find ( xors [ i ] [ j ] ) == map . end ( ) ) map [ xors [ i ] [ j ] ] = { i , j } ; } } int kth_max_e = minHeap . top ( ) ; cout << ( map [ kth_max_e ] [ 0 ] + 1 ) << " ▁ " << ( map [ kth_max_e ] [ 1 ] + 1 ) ; } int main ( ) { int m [ ] [ 3 ] = { { 1 , 2 , 3 } , { 2 , 2 , 1 } , { 2 , 4 , 2 } } ; int k = 1 ; smallestPosition ( m , k , 3 ) ; }