Given a square matrix mat[][] of size N * N, the task is to calculate XOR value of every diagonal elements and find the Kth maximum XOR value obtained.
Note: There are 2 * N – 1 diagonals in the matrix. Starting point of ith diagonal is (min(N, i), (1 + max(i – N, 0))).
Examples:
Input: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, K = 3
Output: 6
Explanation:
XOR of 1st diagonal = 1.
XOR of 2nd diagonal = 4 ^ 2 = 6.
XOR of 3rd diagonal = 7 ^ 5 ^ 3 = 1.
XOR of 4th diagonal = 8 ^ 6 = 14.
XOR of 5th diagonal = 9.Input: mat[][] = {{1, 2}, {4, 5}}, K = 2
Output: 6
Explanation:
XOR of 1st diagonal =1.
XOR of 2nd diagonal = 4 ^ 2 = 6.
XOR of 3rd diagonal = 5.
Approach: Follow the steps below to solve the problem
- Traverse the matrix diagonally.
- For every ith diagonal, starting point is (min(N, i), (1 + max(i – N, 0))).
- Store XOR of each diagonal in a vector.
- Sort the vector.
- Print the Kth maximum value obtained.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find K-th maximum XOR // of any diagonal in the matrix void findXOR(vector<vector<int> > mat, int K) { // Number or rows int N = mat.size(); // Number of columns int M = mat[0].size(); // Store XOR of diagonals vector<int> digXOR; // Traverse each diagonal for (int l = 1; l <= (N + M - 1); l++) { // Starting column of diagonal int s_col = max(0, l - N); // Count total elements in the diagonal int count = min({ l, (M - s_col), N }); // Store XOR of current diagonal int currXOR = 0; for (int j = 0; j < count; j++) { currXOR = (currXOR ^ mat[min(N, l) - j - 1][s_col + j]); } // Push XOR of current diagonal digXOR.push_back(currXOR); } // Sort XOR values of diagonals sort(digXOR.begin(), digXOR.end()); // Print the K-th Maximum XOR cout << digXOR[N + M - 1 - K]; } // Driver Code int main() { vector<vector<int> > mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int K = 3; findXOR(mat, K); return 0; } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG { // Function to find K-th maximum XOR // of any diagonal in the matrix static void findXOR(int[][] mat, int K) { // Number or rows int N = mat.length; // Number of columns int M = mat[0].length; // Store XOR of diagonals ArrayList<Integer> digXOR = new ArrayList<Integer>(); // Traverse each diagonal for (int l = 1; l <= (N + M - 1); l++) { // Starting column of diagonal int s_col = Math.max(0, l - N); // Count total elements in the diagonal int count = Math.min( l, Math.min((M - s_col), N)); // Store XOR of current diagonal int currXOR = 0; for (int j = 0; j < count; j++) { currXOR = (currXOR ^ mat[(Math.min(N, l) - j - 1)][s_col + j]); } // Push XOR of current diagonal digXOR.add(currXOR); } // Sort XOR values of diagonals Collections.sort(digXOR); // Print the K-th Maximum XOR System.out.print(digXOR.get(N + M - 1 - K)); } // Driver Code public static void main(String[] args) { int[][] mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int K = 3; findXOR(mat, K); } } // This code is contributed by code_hunt. |
Python3
# Python3 Program to implement # the above approach # Function to find K-th maximum XOR # of any diagonal in the matrix def findXOR(mat, K): # Number or rows N = len(mat) # Number of columns M = len(mat[0]) # Store XOR of diagonals digXOR = [] # Traverse each diagonal for l in range(1, N + M, 1): # Starting column of diagonal s_col = max(0, l - N) # Count total elements in the diagonal count = min([l, (M - s_col), N]) # Store XOR of current diagonal currXOR = 0 for j in range(count): currXOR = (currXOR ^ mat[min(N, l) - j - 1][s_col + j]) # Push XOR of current diagonal digXOR.append(currXOR) # Sort XOR values of diagonals digXOR.sort(reverse=False) # Print the K-th Maximum XOR print(digXOR[N + M - 1 - K]) # Driver Code if __name__ == '__main__': mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] K = 3 findXOR(mat, K) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find K-th maximum XOR // of any diagonal in the matrix static void findXOR(int[,]mat, int K) { // Number or rows int N = mat.GetLength(0); // Number of columns int M = mat.GetLength(1); // Store XOR of diagonals List<int> digXOR = new List<int>(); // Traverse each diagonal for(int l = 1; l <= (N + M - 1); l++) { // Starting column of diagonal int s_col = Math.Max(0, l - N); // Count total elements in the diagonal int count = Math.Min(l, Math.Min((M - s_col), N)); // Store XOR of current diagonal int currXOR = 0; for(int j = 0; j < count; j++) { currXOR = (currXOR ^ mat[(Math.Min(N, l) - j - 1), s_col + j]); } // Push XOR of current diagonal digXOR.Add(currXOR); } // Sort XOR values of diagonals digXOR.Sort(); // Print the K-th Maximum XOR Console.Write(digXOR[N + M - 1 - K]); } // Driver Code public static void Main(String[] args) { int[,] mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int K = 3; findXOR(mat, K); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript Program to implement // the above approach // Function to find K-th maximum XOR // of any diagonal in the matrix function findXOR(mat, K) { // Number or rows let N = mat.length; // Number of columns let M = mat[0].length; // Store XOR of diagonals let digXOR = []; // Traverse each diagonal for (let l = 1; l <= (N + M - 1); l++) { // Starting column of diagonal let s_col = Math.max(0, l - N); // Count total elements in the diagonal let count = Math.min(l, (M - s_col), N); // Store XOR of current diagonal let currXOR = 0; for (let j = 0; j < count; j++) { currXOR = (currXOR ^ mat[(Math.min(N, l) - j - 1)][s_col + j]); } // Push XOR of current diagonal digXOR.push(currXOR); } // Sort XOR values of diagonals digXOR.sort((a, b) => a - b); // Print the K-th Maximum XOR document.write(digXOR[N + M - 1 - K]); } // Driver Code let mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; let K = 3; findXOR(mat, K); // This code is contributed by gfgking. </script> |
Output:
6
Time Complexity: O(N * M)
Space Complexity: O(N * M)
Take a part in the ongoing discussion
