Smallest submatrix with Kth maximum XOR | C # Program for the above approach ; Function to print smallest index of Kth maximum Xor value of submatrices ; Dimensions of matrix ; Stores XOR values for every index ; Min heap to find the kth maximum XOR value ; Stores indices for corresponding XOR values ; Traversing matrix to calculate XOR values ; Insert calculated value in Min Heap ; If size exceeds k ; Remove the minimum ; Store smallest index containing xor [ i , j ] ; Stores the kth maximum element ; Print the required index ; Driver Code ; Function call
using System ; using System . Collections . Generic ; class GFG { static void smallestPosition ( int [ , ] m , int k ) { int n = m . GetLength ( 0 ) ; int mm = m . GetLength ( 1 ) ; int [ , ] xor = new int [ n , mm ] ; List < int > minHeap = new List < int > ( ) ; Dictionary < int , int [ ] > map = new Dictionary < int , int [ ] > ( ) ; 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 ; minHeap . Add ( xor [ i , j ] ) ; minHeap . Sort ( ) ; if ( minHeap . Count > k ) { minHeap . RemoveAt ( 0 ) ; } if ( ! map . ContainsKey ( xor [ i , j ] ) ) map . Add ( xor [ i , j ] , new int [ ] { i , j } ) ; } } minHeap . Sort ( ) ; int kth_max_e = minHeap [ 0 ] ; Console . WriteLine ( ( map [ kth_max_e ] [ 0 ] + 1 ) + " ▁ " + ( map [ kth_max_e ] [ 1 ] + 1 ) ) ; } public static void Main ( String [ ] args ) { int [ , ] m = { { 1 , 2 , 3 } , { 2 , 2 , 1 } , { 2 , 4 , 2 } } ; int k = 1 ; smallestPosition ( m , k ) ; } }