Hi,
I don't think Dave's solution is correct.
How does the algorithm work for
1 1
1 0
?
Lei
On Nov 27, 2007 4:35 PM, chandra kumar <[EMAIL PROTECTED]> wrote:
> Hey,
> You assumed that you can store -1, but that is not possible in a bit
> array (i.e., if the question states that the array can contain either 0 or 1
> and nothing more than that). But if the array can contain other numbers as
> you assumed then your solution will work. But the solution that Dave
> mentioned seemed to be assuming that the array cannot contain any other
> element and still need not require any extra memory. That's why I'm posting
> all my doubts to him. If this thread can come up with a solution like that
> then it is really good.
>
>
> Thanks and Regards,
> K.V.Chandra Kumar.
>
>
> On 26/11/2007, James Fang <[EMAIL PROTECTED]> wrote:
> >
> >
> >
> >
> >
> > The below algorithm cost 3*O(m*n)+NumberOfInitialZeros*( O(m)+o(n) )
> >
> >
> >
> >
> =================================================================================================================================================================
> >
> >
> >
> > No matter the array can hold other elements or not, you can always use
> auxiliary memory space to make it store more than 0&1, suppose it is a M*N
> array,
> >
> > initializing the auxiliary space will cost O(m*n).
> >
> >
> >
> > and the algorithm can be described as follow:
> >
> >
> >
> > for(int i=0; i<n; ++i)
> >
> > for(int j=0; j<m; ++j)
> >
> > {
> >
> > if( array[i][j] == 0)
> >
> > {
> >
> > for(int k=0;k<n;++k)
> >
> > {
> >
> > if( array[k][j] != 0 ) array[k][j]=-1;
> >
> > }
> >
> > for(int l=0;l<m;++l)
> >
> > {
> >
> > if( array[i][l] != 0 ) array[i][l]=-1;
> >
> > }
> >
> > array[i][j] = -1;
> >
> > }
> >
> > }
> >
> > for(int i=0;i<n;++i)
> >
> > for(int j=0;j<m;++j)
> >
> > if(array[i][j]==-1)
> >
> > array[i][j]=0;
> >
> >
> >
> >
> > Best Regards,
> > James Fang
> >
> > ________________________________
>
> >
> >
> > 发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
> chandra kumar
> > 发送时间: 2007年11月23 日 21:58
> >
> >
> >
> > 收件人: algogeeks@googlegroups.com
> > 主题: [algogeeks] Re: NxN matrix
> >
> >
> >
> >
> >
> >
> >
> > Hi, as I understood the question goes like this (I also face this problem
> earlier)...
> >
> >
> > Given an array of 0s and 1s (whether the array can contain any other
> element apart from 0 and 1 is not mentioned in the question posted, but to
> make it hard people say that the array cannot hold element other then 0 and
> 1, basically a bit array ) . You need to change the given array such that
> each row and column that have a 0 initially should have all 0s in it.
> >
> >
> > e.g.
> >
> >
> > 1 1 1 1 1 0 1 1
> >
> >
> > 1 0 1 1 0 0 0 0
> >
> >
> > 1 1 1 1 ====> 1 0 1 1
> >
> >
> > 1 1 1 1 1 0 1 1
> >
> >
> >
> >
> >
> > Thanks and Regards,
> >
> >
> > K.V.Chandra Kumar
> >
> >
> >
> >
> > On 23/11/2007, MJ < [EMAIL PROTECTED]> wrote:
> >
> >
> > HI Chandra,
> >
> > As per the problem statement
> >
> > "Given an array of 0's and 1's whenever you encounter an 0 make
> > corresponding column and row elements 0. "
> >
> > Does it mean make all the rows and column zero or only last row and
> > column elemnt zero??
> > could you reframe the problem statement with more details or an
> > example.
> >
> > Thank YOu,
> > Mayur
> >
> > On Nov 23, 1:20 pm, "chandra kumar" <[EMAIL PROTECTED] >
> > wrote:
> > > I have some questions in case 2.... questions inlined..
> > >
> > > Thanks and regards,
> > > K.V.Chandra kumar.
> > >
> > > On 22/11/2007, Dave < [EMAIL PROTECTED]> wrote:
> > >
> > >
> > >
> > >
> > >
> > > > Case 1
> > > > Start:
> > > > 0 1 1
> > > > 1 1 1
> > > > 1 1 1
> > >
> > > > After first scan:
> > > > 0 1 0
> > > > 1 1 1
> > > > 0 1 1
> > >
> > > > After second scan:
> > > > 0 1 0
> > > > 0 1 1
> > > > 0 1 1
> > >
> > > > After third scan:
> > > > 0 0 0
> > > > 0 1 1
> > > > 0 1 1
> > >
> > > > Case 2
> > > > Start:
> > > > 1 1 0
> > > > 1 1 1
> > > > 0 1 1
> > >
> > > > After first scan:
> > > > 0 1 0 how did we get 0 in the first row first column, we
> > > > should only alter the last row and column, right?
> > > > 1 1 1
> > > > 0 1 0
> > >
> > > > After second scan:
> > > > 0 0 0 how did we get these zero, only columns are to be
> > > > changed, right?
> > > > 0 1 1
> > > > 0 0 0
> > >
> > > > After third scan:
> > > > 0 0 0
> > > > 0 1 0 how did we get this as, ast element is ignored,
> right?
> > > > 0 0 0
> > >
> > > > Hope this helps.
> > > > Dave
> > >
> > > > On Nov 22, 9:34 am, "chandra kumar" < [EMAIL PROTECTED]>
> > > > wrote:
> > > > > Hi Dave,
> > > > > Can you explain your algo for these 2 cases...
> > >
> > > > > 0 1 1 1 1 0
> > > > > 1 1 1 1 1 1
> > > > > 1 1 1 0 1 1
> > >
> > > > > Please explain me in steps cause we tried the same problem and
> can't
> > > > get
> > > > > it done for without using extra space. ( we used 1 extra space, if
> the
> > > > > array can contain only 0 or 1 and no other number, otherwise we
> store
> > > > some
> > > > > other number indicating a yet to become zero and proceed, in the
> later
> > > > case
> > > > > we need no extra space )
> > > > > Thanks and Regards,
> > > > > K.V.Chandra Kumar
> > >
> > > > > On 15/11/2007, Dave < [EMAIL PROTECTED]> wrote:
> > >
> > > > > > Scan the array. If the i,j element is zero, set the last element
> of
> > > > > > row i and the last element of column j to zero. Then, scan the
> last
> > > > > > row, ignoring the last element, and zero every column that ends
> with a
> > > > > > zero. Similarly, scan the last column, ignoring the last element,
> and
> > > > > > zero every row that ends with a zero. This touches every element
> at
> > > > > > most 3 times; i.e., if the array has m rows and n columns, the
> > > > > > algorithm is O(1) in space and O(m*n) in time.
> > >
> > > > > > Dave
> > >
> > > > > > On Nov 14, 1:27 pm, geekko < [EMAIL PROTECTED]> wrote:
> > > > > > > Given an array of 0's and 1's whenever you encounter an 0 make
> > > > > > > corresponding column and row elements 0. How could you do that
> > > > > > > efficiently(minimum time and minimum space complexity)? This
> > > > question
> > > > > > > is taken from placementsindia.blogspot.com- Hide quoted text -
> > >
> > > > > - Show quoted text -- Hide quoted text -
> > >
> > > - Show quoted text -
> >
> >
> >
> >
> >
> >
> >
> > > >
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
