Lets say the given matrix M is :- a1,1 a1,2 .... a1,c a2,1 a2,2 ..... a2,c . . . ar,1 ar,2 ... ar,c
I think matrix M can be converted to a null matrix if, i) all the elements of a row i are of the form (Ki+2^q) for some constant Ki and any non negative integer q. ii) Property (i) is satisfied for each of the r rows of the matrix. Converting row1 to zero *************************** After that we can convert elements of row 1 by K1 (b) operations to convert the elements of the form 2^q for any non negative integer. And then apply sufficient number of (a) operation to make them identical and then again apply sufficient number (b) operations to make the elements of row1 to zero. Now we have reduced the rXc matrix to (r-1)Xc matrix (all first row elements has been converted to zero). Similarly we can proceed for row2 to row r making them all zero. _dufus On Aug 25, 11:43 pm, ankur aggarwal <[email protected]> wrote: > I've always wanted to feel the excitement in these interviews. I got a > chance, and I liked it. > > Here is the question: > > You are given a matrix: r rows, c cols. r x c matrix. > > Now they all have positive integers. Assume that the computer has no > overflow, it can store all possible integer values. > > Now there are only two operations you can perform on the matrix: > > a. Multiply one whole column (of size r elements) by 2 aij = aij * 2 > b. Decrement a whole row (of size c elements) by 1. aij = aij - 1 > > Now you are required to find out if it's possible with these operations to > convert this matrix into the O matrix. (one with all zeroes in it.) > > If so, how do you solve it? Or when do you decide to terminate? > > give the algo.. > not the code. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
