[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time
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
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
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 -~--~~~~--~~--~--~---