Number of ways to reach the end of matrix with non-zero AND value

Given an N * N matrix arr[][] consisting of non-negative integers, the task is to find the number of ways to reach arr[N – 1][N – 1] with a non-zero AND value starting from the arr[0][0] by going down or right in every move. Whenever a cell arr[i][j] is reached, ‘AND’ value is updated as currentVal & arr[i][j].

Examples: 

Input: arr[][] = { 
{1, 1, 1}, 
{1, 1, 1}, 
{1, 1, 1}}
Output: 6 
All the paths will give non-zero and value. 
Thus, number of ways equals 6.
Input: arr[][] = { 
{1, 1, 2}, 
{1, 2, 1}, 
{2, 1, 1}} 
Output: 0  

Approach: This problem can be solved using dynamic programming. First, we need to decide the states of the DP. For every cell arr[i][j] and a number X, we will store the number of ways to reach the arr[N – 1][N – 1] from arr[i][j] with non-zero AND where X is the AND value of path till now. Thus, our solution will use 3-dimensional dynamic programming, two for the coordinates of the cells and one for X.
The required recurrence relation is: 

dp[i][j][X] = dp[i][j + 1][X & arr[i][j]] + dp[i + 1][j][X & arr[i][j]]  

Below is the implementation of the above approach:  

1

Time Complexity: O(n²)

Auxiliary Space: O(n⁴ * maxV)