Welcome back, this article isn't a review on hollywood blockbuster si-fi "The Matrix", but this is all about fun with the basic math element Matrices. During your grade school you might have played around with matrices, by applying basic operations, using different formulae, proving well defined theorems etc..
But this time we will keep all those things aside and take it to a different level wherein we explore different possible way to read a matrix and try out some interesting tweaks. Let's stimulate all those lakhs of unused neurons in our brains for the first time ( and this is a true fact) .
Here is the collection of few programming problems on matrices which I found on web, books and from friends. try to solve these using minimum number of loops, use recursion and achieve the best, worst case running time.
The problems are arranged on the basis of difficulty, moving from easier ones to difficult.
1) Given a M*N matrix of integers, convert all the integers in a row or column to zero, which already has a "Zero" in the input matrix.
2) Given a M*N matrix of integers, write a program to read the matrix in a circular way, starting from inside-out.
3) Given a M*N matrix of integers, write a program to read the matrix in a zig-zag way.
Note : This way of reading the matrix is used in Run Length Coding of JPEG image compression technique.
4) Given a M*N matrix of integers having both +ve and -ve numbers, write a program to find a sub-matrix with the maximum sum
5) Given a matrix from Sudoku puzzle, write a program to check whether the given matrix is a valid Sudoku puzzle or not by without solving the puzzle. Here we assume that there could be invalid input matrices.
That's all for now. Sharpen your pencil, take a sheet of paper ... Happy coding :-)
But this time we will keep all those things aside and take it to a different level wherein we explore different possible way to read a matrix and try out some interesting tweaks. Let's stimulate all those lakhs of unused neurons in our brains for the first time ( and this is a true fact) .
Here is the collection of few programming problems on matrices which I found on web, books and from friends. try to solve these using minimum number of loops, use recursion and achieve the best, worst case running time.
The problems are arranged on the basis of difficulty, moving from easier ones to difficult.
1) Given a M*N matrix of integers, convert all the integers in a row or column to zero, which already has a "Zero" in the input matrix.
2) Given a M*N matrix of integers, write a program to read the matrix in a circular way, starting from inside-out.
3) Given a M*N matrix of integers, write a program to read the matrix in a zig-zag way.
Note : This way of reading the matrix is used in Run Length Coding of JPEG image compression technique.
4) Given a M*N matrix of integers having both +ve and -ve numbers, write a program to find a sub-matrix with the maximum sum
5) Given a matrix from Sudoku puzzle, write a program to check whether the given matrix is a valid Sudoku puzzle or not by without solving the puzzle. Here we assume that there could be invalid input matrices.
That's all for now. Sharpen your pencil, take a sheet of paper ... Happy coding :-)
Vijay, Please post the solution also...!
ReplyDeleteHi Vikas,
ReplyDeleteTo be frank I have resolved only first 3 of them, but the solutions for all of the above are available on net.
After all why do we have google for :-)
This comment has been removed by the author.
ReplyDeleteHi, Here is the solution for 3rd puzzle.
ReplyDeleteTo make the code easily understandable,the program is made to work only for square matrices(m==n), which can be made to work for non square matrices also with little modifications.
The program runs in O(n^2) time.
Note : Input array is hard coded.
//----------------------------------------------
void compute(int& ,int& ,int& ,int& ,int& ,int& ,bool& ,bool& );
void main()
{
int mat[5][5] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};
int count = 0 ;
int m , n ;
m = 5;
n = 5 ;
int cmin,cmax,rmin,rmax ;
cmin=cmax=rmin=rmax = 0 ;
bool flip,inverse ;
flip = inverse = 0 ;
int c,r;
c=r=0;
while(count != (m*n))
{
if(!flip)
{
(!inverse)?(c=cmin, r=rmax):(c=cmin, r=rmax);
while(c<=cmax && r>= rmin)
{
cout<=cmin && r<=rmax)
{
cout<<mat[r][c]<<",";
c--,r++;
count++;
}
compute(rmax,rmin,cmax,cmin,m,n,inverse,flip);
}
}
getch();
}
void compute(int& rmax,int& rmin,int& cmax,int& cmin,int& m,int& n,bool& inverse,bool& flip)
{
cout<<"\n";
flip = !flip;
inverse = (rmax== (m-1) && cmax == (n-1)) ? true : false ;
(!inverse)?(rmax++,cmax++):(rmin++,cmin++);
}
//----------------------------------------------