[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time

2009-10-10 Thread Ramaswamy R
Whats with the intersection point? Intersection of what two things are we
talking about here? Row of 1s and column of 1s?

On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote:


 There is a n x n grid of 1's and 0's. Find the i, where i is the row
 containing all 1's, except the intersection point. Should do it in
 less than 25 comparisons?

 



-- 
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).

http://sites.google.com/site/ramaswamyr

--~--~-~--~~~---~--~~
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 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---



[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time

2009-10-10 Thread Manisha

By intersection point, I mean intersection of ith row and ith coulmn.
For instance,
1  0  0
1  1  1
1  1   0
Here the answer should be 3 as 3rd row contain all 1's except(3,3).

On Oct 10, 9:15 pm, Ramaswamy R ramaswam...@gmail.com wrote:
 Whats with the intersection point? Intersection of what two things are we
 talking about here? Row of 1s and column of 1s?

 On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote:

  There is a n x n grid of 1's and 0's. Find the i, where i is the row
  containing all 1's, except the intersection point. Should do it in
  less than 25 comparisons?

 --
 Yesterday is History.
 Tomorrow is a Mystery.
 Today is a Gift! That is why it is called the Present :).

 http://sites.google.com/site/ramaswamyr

--~--~-~--~~~---~--~~
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 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---



[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time

2009-10-10 Thread Ramaswamy R
On another thought, constant time complexity would not be possible with no
constraints on the size of the matrix or any limitation on what possible
data it would have.
It wouldn't be possible to do it in 25 comparisons for a 1 Million x 1
Million grid. If there is no restriction on the data as well then we would
be forced to scan through (in whatever way) all the n^2 values.

On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote:


 There is a n x n grid of 1's and 0's. Find the i, where i is the row
 containing all 1's, except the intersection point. Should do it in
 less than 25 comparisons?

 



-- 
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).

http://sites.google.com/site/ramaswamyr

--~--~-~--~~~---~--~~
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 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---