Maximum XOR of a path from top-left to bottom-right cell of given Matrix

0 0 7 minutes read

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 Code
int 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 Code
if __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 approach
using 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 Code
public 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 approach
 
function 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>

Output

Time Complexity: O(2^N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!