Given a matrix, mat[][] of dimensions N * M, the task is to print the maximum bitwise XOR value that can be obtained for a path from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1) of the given matrix. Only possible moves from any cell (i, j) are (i + 1, j) and (i, j + 1).
Note: Bitwise XOR value of a path is defined as the bitwise XOR of all possible elements on that path.
Examples:
Input: mat[][] = {{3, 2, 1}, {6, 5, 4}, {7, 8, 9}}
Output: 13
Explanation:
Possible paths from (0, 0) to (N – 1, M – 1) and their bitwise XOR values are:
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) having XOR value 13.
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2) having XOR value 9.
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2) having XOR value 13.
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) having XOR value 5.
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) having XOR value 1.
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) having XOR value 3
Therefore, the maximum bitwise XOR value for all possible paths is 13.
Input: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Output: 15
Approach: The idea is to generate all possible paths from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1) of the given matrix using Recursion and print the maximum XOR value of all possible paths. The following are the recurrence relations and their base cases:
Recurrence relation:
printMaxXOR(i, j, xorValue) = max(printMaxXOR(i – 1, j, xorValue ^ mat[i][j]), printMaxXOR(i, j – 1, xorValue ^ mat[i][j]))Base Case:
if i = 0 and j = 0: return mat[i][j] ^ xorValue
if i = 0: return printMaxXOR(i, j – 1, mat[i][j] ^ xorValue)
if j = 0: return printMaxXOR(i – 1, j, mat[i][j] ^ xorValue)
Follow the steps below to solve the problem:
- Initialize a variable, say xorValue to store the bitwise XOR of all possible elements on the path from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1).
- Use the above recurrence relation to find the maximum XOR value of all possible paths from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1).
- Finally, print the maximum XOR value of all possible paths from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1).
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 print maximum XOR// value of all possible path// from (0, 0) to (N - 1, M - 1)int printMaxXOR(vector<vector<int> >& mat, int i, int j, int xorValue){ // Base case if (i == 0 && j == 0) { return mat[i][j] ^ xorValue; } // Base case if (i == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) return printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue); } if (j == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) return printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue); } // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) int X = printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue); // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) int Y = printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue); return max(X, Y);}// Driver Codeint main(){ vector<vector<int> > mat = { { 3, 2, 1 }, { 6, 5, 4 }, { 7, 8, 9 } }; int N = mat.size(); int M = mat[0].size(); // Stores bitwise XOR of // all elements on each possible path int xorValue = 0; cout << printMaxXOR(mat, N - 1, M - 1, xorValue);} |
Java
import java.io.*;import java.util.*;class GFG { public static int printMaxXOR(int[][] mat, int i, int j, int xorValue) { // Base case if (i == 0 && j == 0) { return mat[i][j] ^ xorValue; } // Base case if (i == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) return printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue); } if (j == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) return printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue); } // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) int X = printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue); // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) int Y = printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue); return Math.max(X, Y); } // Driver Code public static void main(String[] args) { int[][] mat = { { 3, 2, 1 }, { 6, 5, 4 }, { 7, 8, 9 } }; int N = mat.length; int M = mat[0].length; // Stores bitwise XOR of // all elements on each possible path int xorValue = 0; System.out.println( printMaxXOR(mat, N - 1, M - 1, xorValue)); } // This code is contributed by hemanth gadarla} |
Python3
# Python 3 program to implement# the above approach# Function to print maximum XOR# value of all possible path# from (0, 0) to (N - 1, M - 1)def printMaxXOR(mat, i, j, xorValue): # Base case if (i == 0 and j == 0): return mat[i][j] ^ xorValue # Base case if (i == 0): # Stores maximum XOR value # by selecting path from (i, j) # to (i, j - 1) return printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue) if (j == 0): # Stores maximum XOR value # by selecting path from (i, j) # to (i - 1, j) return printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue) # Stores maximum XOR value # by selecting path from (i, j) # to (i - 1, j) X = printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue) # Stores maximum XOR value # by selecting path from (i, j) # to (i, j - 1) Y = printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue) return max(X, Y) # Driver Codeif __name__ == "__main__": mat = [[3, 2, 1], [6, 5, 4], [7, 8, 9]] N = len(mat) M = len(mat[0]) # Stores bitwise XOR of # all elements on each # possible path xorValue = 0 print(printMaxXOR(mat, N - 1, M - 1, xorValue))# This code is contributed by Chitranayal |
C#
// C# program to implement the // above approachusing System;class GFG{ public static int printMaxXOR(int[,] mat, int i, int j, int xorValue){ // Base case if (i == 0 && j == 0) { return mat[i,j] ^ xorValue; } // Base case if (i == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) return printMaxXOR(mat, i, j - 1, mat[i,j] ^ xorValue); } if (j == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) return printMaxXOR(mat, i - 1, j, mat[i,j] ^ xorValue); } // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) int X = printMaxXOR(mat, i - 1, j, mat[i,j] ^ xorValue); // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) int Y = printMaxXOR(mat, i, j - 1, mat[i,j] ^ xorValue); return Math.Max(X, Y);} // Driver Codepublic static void Main(String[] args){ int[,] mat = {{3, 2, 1}, {6, 5, 4}, {7, 8, 9}}; int N = mat.GetLength(0); int M = mat.GetLength(1); // Stores bitwise XOR of // all elements on each // possible path int xorValue = 0; Console.WriteLine(printMaxXOR(mat, N - 1, M - 1, xorValue));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program to implement// the above approachfunction printMaxXOR(mat, i, j, xorValue) { // Base case if (i == 0 && j == 0) { return mat[i][j] ^ xorValue; } // Base case if (i == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) return printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue); } if (j == 0) { // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) return printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue); } // Stores maximum XOR value // by selecting path from (i, j) // to (i - 1, j) let X = printMaxXOR(mat, i - 1, j, mat[i][j] ^ xorValue); // Stores maximum XOR value // by selecting path from (i, j) // to (i, j - 1) let Y = printMaxXOR(mat, i, j - 1, mat[i][j] ^ xorValue); return Math.max(X, Y); } // Driver Code let mat = [[ 3, 2, 1 ], [ 6, 5, 4 ], [ 7, 8, 9 ]]; let N = mat.length; let M = mat[0].length; // Stores bitwise XOR of // all elements on each possible path let xorValue = 0; document.write( printMaxXOR(mat, N - 1, M - 1, xorValue)); </script> |
13
Time Complexity: O(2N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
