Saturday 13 December 2014

Matrix Tracing


A very clean single function to solve HackerRank's contest that has been explained in V. Anton Spraul vedio.

Problem Statement
A word from the English dictionary is taken and arranged as a matrix. e.g. "MATHEMATICS"
MATHE 
ATHEM 
THEMA 
HEMAT 
EMATI 
MATIC 
ATICS
There are many ways to trace this matrix in a way that helps you construct this word. You start tracing the matrix from the top-left position and at each iteration, you either move RIGHT or DOWN, and ultimately reach the bottom-right of the matrix. It is assured that any such tracing generates the same word. How many such tracings can be possible for a given word of length m+n-1 written as a matrix of size m * n? 

Solution:
int trace(int row, int col)
{
static int count = 0;

if (row == 1 && col == 1)
count++;
else
{
if (row <= 0 || col <= 0)
return -1;
trace(row, col - 1);
trace(row - 1, col);
}
return count;
}

Input:
  trace( 4 , 3 );

Output:
  10

Explain:
  Recursive upward traversal as shown in the next figure.



7 comments:

  1. hello sir but this approach doesn't work for all test cases.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. waiting for your reply for correct algorithm.

    ReplyDelete
  4. Would you please forward me the uncovered test cases?

    ReplyDelete
    Replies
    1. actually it showing TLE for some test case and runtime error for some other test case.

      Delete
  5. For each test case the value of the static variable is preserved how can i again made it to zero if . i can't find how to do that can you explain me please?

    ReplyDelete
  6. can you please provide me the code for the same?
    I am waiting for your reply.

    ReplyDelete