Given a matrix m[][] of dimensions N × M and an integer K, calculate XOR(i, j) which is equal to the Bitwise Xor of all elements of submatrix from indices (1, 1) to (i, j)), for every index of the matrix. The task is to find the submatrix {(1, 1), …, (i, j)} having Kth maximum XOR(i, j) value. If multiple such submatrices exist, then print the smallest one.
Note: Consider the starting index of the matrix from (1, 1).
Examples:
Input: m[][] = {{1, 2}, {2, 3}}, K = 2
Output: 1 2
Explanation:
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
Hence, the 2nd maximum value is 3 at position [1, 2].Input: m[][] = {{1, 2, 3}, {2, 2, 1}, {2, 4, 2} }, k = 1
Output: 3 2
Approach: The idea is to find XOR (i, j) using Dynamic Programming.
- Calculate the bitwise XOR(i, j) as xor[i][j] = xor[i-1][j] ^ xor[i][j-1] ^ xor[i-1][j-1] ^ m[i][j].
- Store the XOR(i, j) values obtained for respective indices (i, j) in a Map.
- Find the Kth maximum of all XOR(i, j) values using a Min-heap of size K.
- Find the smallest index (i, j) for which XOR(i, j) is equal to the Kth maximum obtained in the above step using the Map.
Below is the implementation of the above approach:
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> |
3 2
Time Complexity: O(N * M * log K)
Auxiliary Space: O(N * M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!