Re: [algogeeks] Challenge
problem solved **thread closed** On Sun, Aug 21, 2011 at 12:16 PM, Sanjay Rajpal wrote: > see array is sorted when all zeros occur before 1s in each row. > > Now see ur input. My algo will work only for sorted array. > > On 8/20/11, rashmi i wrote: > > will your solution work for: > > 0001 > > 0010 > > 0100 > > 0110 > > 1000 > > > > > > On Sun, Aug 21, 2011 at 10:29 AM, sachin sabbarwal < > sweetsachin...@gmail.com > >> wrote: > > > >> yes ,your example is sorted. > >> > >> On Sun, Aug 21, 2011 at 10:24 AM, Jagannath Prasad Das > >> wrote: > >> > what does sorted row means??? > >> > is it > >> > 00011 > >> > 0 > >> > 1 > >> > 0 > >> > where each row is sorted or among the rows also? > >> > On Sun, Aug 21, 2011 at 9:51 AM, Sanjay Rajpal > wrote: > >> >> > >> >> hey see this array is not sorted, I forgot to mention this in my > first > >> >> post, but cleared this in subsequent posts that the rows in the array > >> are > >> >> sorted. > >> >> > >> >> Plz see above posts. > >> >> Sanju > >> >> :) > >> >> > >> >> > >> >> > >> >> On Sat, Aug 20, 2011 at 9:05 PM, Abhishek < > >> mailatabhishekgu...@gmail.com> > >> >> wrote: > >> >>> > >> >>> will this solution also work for.. > >> >>> > >> >>> > >> >>> 0101 > >> >>> 1011 > >> >>> 11010100 > >> >>> 0100 > >> >>> 1001 > >> >>> 0111 > >> >>> > >> >>> plz clear your logic bit more.. > >> >>> > >> >>> -- > >> >>> You received this message because you are subscribed to the Google > >> Groups > >> >>> "Algorithm Geeks" group. > >> >>> To view this discussion on the web visit > >> >>> https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. > >> >>> 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?hl=en. > >> >> > >> >> -- > >> >> 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?hl=en. > >> > > >> > -- > >> > 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?hl=en. > >> > > >> > >> > >> > >> -- > >> Sachin Sabbarwal > >> Nit Kurukshetra > >> III year > >> > >> -- > >> 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?hl=en. > >> > >> > > > > > > -- > > R@$!-! > > "DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS." > > > > -- > > 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?hl=en. > > > > > > > -- > Sanju > :) > > -- > 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?hl=en. > > -- 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?hl=en.
Re: [algogeeks] Challenge
see array is sorted when all zeros occur before 1s in each row. Now see ur input. My algo will work only for sorted array. On 8/20/11, rashmi i wrote: > will your solution work for: > 0001 > 0010 > 0100 > 0110 > 1000 > > > On Sun, Aug 21, 2011 at 10:29 AM, sachin sabbarwal > wrote: > >> yes ,your example is sorted. >> >> On Sun, Aug 21, 2011 at 10:24 AM, Jagannath Prasad Das >> wrote: >> > what does sorted row means??? >> > is it >> > 00011 >> > 0 >> > 1 >> > 0 >> > where each row is sorted or among the rows also? >> > On Sun, Aug 21, 2011 at 9:51 AM, Sanjay Rajpal wrote: >> >> >> >> hey see this array is not sorted, I forgot to mention this in my first >> >> post, but cleared this in subsequent posts that the rows in the array >> are >> >> sorted. >> >> >> >> Plz see above posts. >> >> Sanju >> >> :) >> >> >> >> >> >> >> >> On Sat, Aug 20, 2011 at 9:05 PM, Abhishek < >> mailatabhishekgu...@gmail.com> >> >> wrote: >> >>> >> >>> will this solution also work for.. >> >>> >> >>> >> >>> 0101 >> >>> 1011 >> >>> 11010100 >> >>> 0100 >> >>> 1001 >> >>> 0111 >> >>> >> >>> plz clear your logic bit more.. >> >>> >> >>> -- >> >>> You received this message because you are subscribed to the Google >> Groups >> >>> "Algorithm Geeks" group. >> >>> To view this discussion on the web visit >> >>> https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. >> >>> 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?hl=en. >> >> >> >> -- >> >> 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?hl=en. >> > >> > -- >> > 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?hl=en. >> > >> >> >> >> -- >> Sachin Sabbarwal >> Nit Kurukshetra >> III year >> >> -- >> 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?hl=en. >> >> > > > -- > R@$!-! > "DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS." > > -- > 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?hl=en. > > -- Sanju :) -- 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?hl=en.
Re: [algogeeks] Challenge
your matrix isn't sorted!!! a sorted matrix is 0001 0011 etc -- Forwarded message -- From: rashmi i Date: Sun, Aug 21, 2011 at 11:52 AM Subject: Re: [algogeeks] Challenge To: algogeeks@googlegroups.com will your solution work for: 0001 0010 0100 0110 1000 On Sun, Aug 21, 2011 at 10:29 AM, sachin sabbarwal wrote: > yes ,your example is sorted. > > On Sun, Aug 21, 2011 at 10:24 AM, Jagannath Prasad Das > wrote: > > what does sorted row means??? > > is it > > 00011 > > 0 > > 1 > > 0 > > where each row is sorted or among the rows also? > > On Sun, Aug 21, 2011 at 9:51 AM, Sanjay Rajpal wrote: > >> > >> hey see this array is not sorted, I forgot to mention this in my first > >> post, but cleared this in subsequent posts that the rows in the array > are > >> sorted. > >> > >> Plz see above posts. > >> Sanju > >> :) > >> > >> > >> > >> On Sat, Aug 20, 2011 at 9:05 PM, Abhishek < > mailatabhishekgu...@gmail.com> > >> wrote: > >>> > >>> will this solution also work for.. > >>> > >>> > >>> 0101 > >>> 1011 > >>> 11010100 > >>> 0100 > >>> 1001 > >>> 0111 > >>> > >>> plz clear your logic bit more.. > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "Algorithm Geeks" group. > >>> To view this discussion on the web visit > >>> https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. > >>> 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?hl=en. > >> > >> -- > >> 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?hl=en. > > > > -- > > 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?hl=en. > > > > > > -- > Sachin Sabbarwal > Nit Kurukshetra > III year > > -- > 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?hl=en. > > -- R@$!-! "DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS." -- 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?hl=en. -- 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?hl=en.
Re: [algogeeks] Challenge
will your solution work for: 0001 0010 0100 0110 1000 On Sun, Aug 21, 2011 at 10:29 AM, sachin sabbarwal wrote: > yes ,your example is sorted. > > On Sun, Aug 21, 2011 at 10:24 AM, Jagannath Prasad Das > wrote: > > what does sorted row means??? > > is it > > 00011 > > 0 > > 1 > > 0 > > where each row is sorted or among the rows also? > > On Sun, Aug 21, 2011 at 9:51 AM, Sanjay Rajpal wrote: > >> > >> hey see this array is not sorted, I forgot to mention this in my first > >> post, but cleared this in subsequent posts that the rows in the array > are > >> sorted. > >> > >> Plz see above posts. > >> Sanju > >> :) > >> > >> > >> > >> On Sat, Aug 20, 2011 at 9:05 PM, Abhishek < > mailatabhishekgu...@gmail.com> > >> wrote: > >>> > >>> will this solution also work for.. > >>> > >>> > >>> 0101 > >>> 1011 > >>> 11010100 > >>> 0100 > >>> 1001 > >>> 0111 > >>> > >>> plz clear your logic bit more.. > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "Algorithm Geeks" group. > >>> To view this discussion on the web visit > >>> https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. > >>> 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?hl=en. > >> > >> -- > >> 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?hl=en. > > > > -- > > 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?hl=en. > > > > > > -- > Sachin Sabbarwal > Nit Kurukshetra > III year > > -- > 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?hl=en. > > -- R@$!-! "DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS." -- 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?hl=en.
Re: [algogeeks] Challenge
yes ,your example is sorted. On Sun, Aug 21, 2011 at 10:24 AM, Jagannath Prasad Das wrote: > what does sorted row means??? > is it > 00011 > 0 > 1 > 0 > where each row is sorted or among the rows also? > On Sun, Aug 21, 2011 at 9:51 AM, Sanjay Rajpal wrote: >> >> hey see this array is not sorted, I forgot to mention this in my first >> post, but cleared this in subsequent posts that the rows in the array are >> sorted. >> >> Plz see above posts. >> Sanju >> :) >> >> >> >> On Sat, Aug 20, 2011 at 9:05 PM, Abhishek >> wrote: >>> >>> will this solution also work for.. >>> >>> >>> 0101 >>> 1011 >>> 11010100 >>> 0100 >>> 1001 >>> 0111 >>> >>> plz clear your logic bit more.. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. >>> 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?hl=en. >> >> -- >> 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?hl=en. > > -- > 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?hl=en. > -- Sachin Sabbarwal Nit Kurukshetra III year -- 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?hl=en.
Re: [algogeeks] Challenge
yes, this is sorted matrix. Sanju :) On Sat, Aug 20, 2011 at 9:54 PM, Jagannath Prasad Das wrote: > what does sorted row means??? > is it > 00011 > 0 > 1 > 0 > where each row is sorted or among the rows also? > > On Sun, Aug 21, 2011 at 9:51 AM, Sanjay Rajpal wrote: > >> hey see this array is not sorted, I forgot to mention this in my first >> post, but cleared this in subsequent posts that the rows in the array are >> sorted. >> >> Plz see above posts. >> Sanju >> :) >> >> >> >> On Sat, Aug 20, 2011 at 9:05 PM, Abhishek >> wrote: >> >>> will this solution also work for.. >>> >>> >>> 0101 >>> 1011 >>> 11010100 >>> 0100 >>> 1001 >>> 0111 >>> >>> >>> plz clear your logic bit more.. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. >>> >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
what does sorted row means??? is it 00011 0 1 0 where each row is sorted or among the rows also? On Sun, Aug 21, 2011 at 9:51 AM, Sanjay Rajpal wrote: > hey see this array is not sorted, I forgot to mention this in my first > post, but cleared this in subsequent posts that the rows in the array are > sorted. > > Plz see above posts. > Sanju > :) > > > > On Sat, Aug 20, 2011 at 9:05 PM, Abhishek > wrote: > >> will this solution also work for.. >> >> >> 0101 >> 1011 >> 11010100 >> 0100 >> 1001 >> 0111 >> >> >> plz clear your logic bit more.. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. >> >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
hey see this array is not sorted, I forgot to mention this in my first post, but cleared this in subsequent posts that the rows in the array are sorted. Plz see above posts. Sanju :) On Sat, Aug 20, 2011 at 9:05 PM, Abhishek wrote: > will this solution also work for.. > > > 0101 > 1011 > 11010100 > 0100 > 1001 > 0111 > > > plz clear your logic bit more.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. > > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
will this solution also work for.. 0101 1011 11010100 0100 1001 0111 plz clear your logic bit more.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/A8HrLEBIIF8J. 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?hl=en.
Re: [algogeeks] Challenge
@Sanjay awesome aproach frd .. --mac On Sat, Aug 20, 2011 at 3:39 PM, Sanjay Rajpal wrote: > My previous argument was wrong. > > In the worst case, within a row, you may have to traverse the whole row, > and rest other rows for just testing. Therefore O(m+n). > > But if we dont traverse the other rows once we traversed the whole row, it > can be O(n) in the best case. > > > Sanju > :) > > > > On Sat, Aug 20, 2011 at 3:04 AM, Sanjay Rajpal wrote: > >> Got it in the worst case also it will be O(m+n) >> Worst case will be >> 0001 >> 0011 >> 0111 >> >> 0001 >> 0011 >> 0111 >> >> >> at each step just make one comparison and one step towards left, which in >> worst case is >> m comparisons and n increments, so final solution is O(m+n). >> >> Correct me if I am wrong. >> Sanju >> :) >> >> >> >> On Sat, Aug 20, 2011 at 3:00 AM, Shashank Gupta >> wrote: >> >>> In worst case it would be O(m*n).. >>> >>> >>> >>> On Sat, Aug 20, 2011 at 3:27 PM, shady wrote: >>> @Sanjay awesome solution it won't be O(n^2) in worst case, it will be O(m+n) only On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: > Yes, thats right. > I think we can do the following also : > > Lets us assume rows are sorted in increasing order. > > start from first row say i. Traverse the array from the end of the row > towards the beginning till 0 occurs say at position j. > now proceed to the next row i+1, check the value at i+1,j if it is 0, > go to next row i+2,j > else if its 1, then go to left till 0 occurs and store that index of 0 > and follow to the next row. > > In the worst case, it will be O(n^2), but in general its a good > approach i guess. what do u say guys ? > > Average Case O(m+n) ? > > > Sanju > :) > > > > On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: > >> binary search on every row which will give solution in O(m*(logn)) >> >> On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: >> >>> Sorry I forgot to mention that. >>> >>> Sanju >>> :) >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en. >>> >>> >>> >>> -- >>> - >>> $hashank Gupta >>> - >>> Let not a man guard his dignity, but let his dignity guard him. >>> >>> >>> -- >>> 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?hl=en. >>> >> >> > -- > 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?hl=en. > -- thanks --mac -- 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.
Re: [algogeeks] Challenge
My previous argument was wrong. In the worst case, within a row, you may have to traverse the whole row, and rest other rows for just testing. Therefore O(m+n). But if we dont traverse the other rows once we traversed the whole row, it can be O(n) in the best case. Sanju :) On Sat, Aug 20, 2011 at 3:04 AM, Sanjay Rajpal wrote: > Got it in the worst case also it will be O(m+n) > Worst case will be > 0001 > 0011 > 0111 > > 0001 > 0011 > 0111 > > > at each step just make one comparison and one step towards left, which in > worst case is > m comparisons and n increments, so final solution is O(m+n). > > Correct me if I am wrong. > Sanju > :) > > > > On Sat, Aug 20, 2011 at 3:00 AM, Shashank Gupta > wrote: > >> In worst case it would be O(m*n).. >> >> >> >> On Sat, Aug 20, 2011 at 3:27 PM, shady wrote: >> >>> @Sanjay awesome solution >>> it won't be O(n^2) in worst case, it will be O(m+n) only >>> >>> On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: >>> Yes, thats right. I think we can do the following also : Lets us assume rows are sorted in increasing order. start from first row say i. Traverse the array from the end of the row towards the beginning till 0 occurs say at position j. now proceed to the next row i+1, check the value at i+1,j if it is 0, go to next row i+2,j else if its 1, then go to left till 0 occurs and store that index of 0 and follow to the next row. In the worst case, it will be O(n^2), but in general its a good approach i guess. what do u say guys ? Average Case O(m+n) ? Sanju :) On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: > binary search on every row which will give solution in O(m*(logn)) > > On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: > >> Sorry I forgot to mention that. >> >> Sanju >> :) >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en. >>> >>> -- >>> 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?hl=en. >>> >> >> >> >> -- >> - >> $hashank Gupta >> - >> Let not a man guard his dignity, but let his dignity guard him. >> >> >> -- >> 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?hl=en. >> > > -- 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?hl=en.
Re: [algogeeks] Challenge
For each row we wont be traversing all elements from right to left, the total number of comparisons we make for all rows will be equal to n or worst case 2n. So it will be O(m+n) On Sat, Aug 20, 2011 at 3:34 PM, Sanjay Rajpal wrote: > Got it in the worst case also it will be O(m+n) > Worst case will be > 0001 > 0011 > 0111 > > 0001 > 0011 > 0111 > > > at each step just make one comparison and one step towards left, which in > worst case is > m comparisons and n increments, so final solution is O(m+n). > > Correct me if I am wrong. > Sanju > :) > > > > On Sat, Aug 20, 2011 at 3:00 AM, Shashank Gupta > wrote: > >> In worst case it would be O(m*n).. >> >> >> >> On Sat, Aug 20, 2011 at 3:27 PM, shady wrote: >> >>> @Sanjay awesome solution >>> it won't be O(n^2) in worst case, it will be O(m+n) only >>> >>> On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: >>> Yes, thats right. I think we can do the following also : Lets us assume rows are sorted in increasing order. start from first row say i. Traverse the array from the end of the row towards the beginning till 0 occurs say at position j. now proceed to the next row i+1, check the value at i+1,j if it is 0, go to next row i+2,j else if its 1, then go to left till 0 occurs and store that index of 0 and follow to the next row. In the worst case, it will be O(n^2), but in general its a good approach i guess. what do u say guys ? Average Case O(m+n) ? Sanju :) On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: > binary search on every row which will give solution in O(m*(logn)) > > On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: > >> Sorry I forgot to mention that. >> >> Sanju >> :) >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en. >>> >>> -- >>> 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?hl=en. >>> >> >> >> >> -- >> - >> $hashank Gupta >> - >> Let not a man guard his dignity, but let his dignity guard him. >> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
Got it in the worst case also it will be O(m+n) Worst case will be 0001 0011 0111 0001 0011 0111 at each step just make one comparison and one step towards left, which in worst case is m comparisons and n increments, so final solution is O(m+n). Correct me if I am wrong. Sanju :) On Sat, Aug 20, 2011 at 3:00 AM, Shashank Gupta wrote: > In worst case it would be O(m*n).. > > > > On Sat, Aug 20, 2011 at 3:27 PM, shady wrote: > >> @Sanjay awesome solution >> it won't be O(n^2) in worst case, it will be O(m+n) only >> >> On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: >> >>> Yes, thats right. >>> I think we can do the following also : >>> >>> Lets us assume rows are sorted in increasing order. >>> >>> start from first row say i. Traverse the array from the end of the row >>> towards the beginning till 0 occurs say at position j. >>> now proceed to the next row i+1, check the value at i+1,j if it is 0, go >>> to next row i+2,j >>> else if its 1, then go to left till 0 occurs and store that index of 0 >>> and follow to the next row. >>> >>> In the worst case, it will be O(n^2), but in general its a good approach >>> i guess. what do u say guys ? >>> >>> Average Case O(m+n) ? >>> >>> >>> Sanju >>> :) >>> >>> >>> >>> On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: >>> binary search on every row which will give solution in O(m*(logn)) On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: > Sorry I forgot to mention that. > > Sanju > :) > > -- > 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?hl=en. > -- 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?hl=en. >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > > > -- > - > $hashank Gupta > - > Let not a man guard his dignity, but let his dignity guard him. > > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
nope... it is O(m+n) only :) On Sat, Aug 20, 2011 at 3:30 PM, Shashank Gupta wrote: > In worst case it would be O(m*n).. > > > > On Sat, Aug 20, 2011 at 3:27 PM, shady wrote: > >> @Sanjay awesome solution >> it won't be O(n^2) in worst case, it will be O(m+n) only >> >> On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: >> >>> Yes, thats right. >>> I think we can do the following also : >>> >>> Lets us assume rows are sorted in increasing order. >>> >>> start from first row say i. Traverse the array from the end of the row >>> towards the beginning till 0 occurs say at position j. >>> now proceed to the next row i+1, check the value at i+1,j if it is 0, go >>> to next row i+2,j >>> else if its 1, then go to left till 0 occurs and store that index of 0 >>> and follow to the next row. >>> >>> In the worst case, it will be O(n^2), but in general its a good approach >>> i guess. what do u say guys ? >>> >>> Average Case O(m+n) ? >>> >>> >>> Sanju >>> :) >>> >>> >>> >>> On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: >>> binary search on every row which will give solution in O(m*(logn)) On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: > Sorry I forgot to mention that. > > Sanju > :) > > -- > 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?hl=en. > -- 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?hl=en. >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > > > -- > - > $hashank Gupta > - > Let not a man guard his dignity, but let his dignity guard him. > > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
In worst case it would be O(m*n).. On Sat, Aug 20, 2011 at 3:27 PM, shady wrote: > @Sanjay awesome solution > it won't be O(n^2) in worst case, it will be O(m+n) only > > On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: > >> Yes, thats right. >> I think we can do the following also : >> >> Lets us assume rows are sorted in increasing order. >> >> start from first row say i. Traverse the array from the end of the row >> towards the beginning till 0 occurs say at position j. >> now proceed to the next row i+1, check the value at i+1,j if it is 0, go >> to next row i+2,j >> else if its 1, then go to left till 0 occurs and store that index of 0 and >> follow to the next row. >> >> In the worst case, it will be O(n^2), but in general its a good approach i >> guess. what do u say guys ? >> >> Average Case O(m+n) ? >> >> >> Sanju >> :) >> >> >> >> On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: >> >>> binary search on every row which will give solution in O(m*(logn)) >>> >>> On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: >>> Sorry I forgot to mention that. Sanju :) -- 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?hl=en. >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- - $hashank Gupta - Let not a man guard his dignity, but let his dignity guard him. -- 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?hl=en.
Re: [algogeeks] Challenge
yah this is a good approach...but one thing in worst case it would be m^2 instead of n^2 On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: > Yes, thats right. > I think we can do the following also : > > Lets us assume rows are sorted in increasing order. > > start from first row say i. Traverse the array from the end of the row > towards the beginning till 0 occurs say at position j. > now proceed to the next row i+1, check the value at i+1,j if it is 0, go > to next row i+2,j > else if its 1, then go to left till 0 occurs and store that index of 0 and > follow to the next row. > > In the worst case, it will be O(n^2), but in general its a good approach i > guess. what do u say guys ? > > Average Case O(m+n) ? > > > Sanju > :) > > > > On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: > >> binary search on every row which will give solution in O(m*(logn)) >> >> On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: >> >>> Sorry I forgot to mention that. >>> >>> Sanju >>> :) >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
@Sanjay awesome solution it won't be O(n^2) in worst case, it will be O(m+n) only On Sat, Aug 20, 2011 at 3:22 PM, Sanjay Rajpal wrote: > Yes, thats right. > I think we can do the following also : > > Lets us assume rows are sorted in increasing order. > > start from first row say i. Traverse the array from the end of the row > towards the beginning till 0 occurs say at position j. > now proceed to the next row i+1, check the value at i+1,j if it is 0, go > to next row i+2,j > else if its 1, then go to left till 0 occurs and store that index of 0 and > follow to the next row. > > In the worst case, it will be O(n^2), but in general its a good approach i > guess. what do u say guys ? > > Average Case O(m+n) ? > > > Sanju > :) > > > > On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: > >> binary search on every row which will give solution in O(m*(logn)) >> >> On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: >> >>> Sorry I forgot to mention that. >>> >>> Sanju >>> :) >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
Yes, thats right. I think we can do the following also : Lets us assume rows are sorted in increasing order. start from first row say i. Traverse the array from the end of the row towards the beginning till 0 occurs say at position j. now proceed to the next row i+1, check the value at i+1,j if it is 0, go to next row i+2,j else if its 1, then go to left till 0 occurs and store that index of 0 and follow to the next row. In the worst case, it will be O(n^2), but in general its a good approach i guess. what do u say guys ? Average Case O(m+n) ? Sanju :) On Sat, Aug 20, 2011 at 2:47 AM, shady wrote: > binary search on every row which will give solution in O(m*(logn)) > > On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: > >> Sorry I forgot to mention that. >> >> Sanju >> :) >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
binary search on every row which will give solution in O(m*(logn)) On Sat, Aug 20, 2011 at 3:13 PM, Sanjay Rajpal wrote: > Sorry I forgot to mention that. > > Sanju > :) > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
Sorry I forgot to mention that. Sanju :) -- 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?hl=en.
Re: [algogeeks] Challenge
This question has more specification that the rows are sorted. It can be easily solved then. Otherwise its not solvable. On Sat, Aug 20, 2011 at 3:04 PM, shady wrote: > i wonder how is it possible because reading input itself takes O(m*n) > > > On Sat, Aug 20, 2011 at 2:59 PM, Sanjay Rajpal wrote: > >> Yes its O(m+n), but i dont know how :) >> Thats y i posted it here. >> >> >> Sanju >> :) >> >> >> >> On Sat, Aug 20, 2011 at 2:28 AM, Naman Mahor wrote: >> >>> it is O(m+n). sure?? >>> >>> On Sat, Aug 20, 2011 at 2:52 PM, Sanjay Rajpal wrote: >>> We are given a 2-D array of 0s and 1s. We have to determine which row contains maximum no. of 1s in the array in O(m+n); where m - no. of rows and n - no. of columns. Sanju :) -- 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?hl=en. >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- Romil -- 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?hl=en.
Re: [algogeeks] Challenge
i wonder how is it possible because reading input itself takes O(m*n) On Sat, Aug 20, 2011 at 2:59 PM, Sanjay Rajpal wrote: > Yes its O(m+n), but i dont know how :) > Thats y i posted it here. > > > Sanju > :) > > > > On Sat, Aug 20, 2011 at 2:28 AM, Naman Mahor wrote: > >> it is O(m+n). sure?? >> >> On Sat, Aug 20, 2011 at 2:52 PM, Sanjay Rajpal wrote: >> >>>We are given a 2-D array of 0s and 1s. >>> We have to determine which row contains maximum no. of 1s in the array in >>> O(m+n); >>> where m - no. of rows and n - no. of columns. >>> >>> Sanju >>> :) >>> >>> -- >>> 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?hl=en. >>> >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
Yes its O(m+n), but i dont know how :) Thats y i posted it here. Sanju :) On Sat, Aug 20, 2011 at 2:28 AM, Naman Mahor wrote: > it is O(m+n). sure?? > > On Sat, Aug 20, 2011 at 2:52 PM, Sanjay Rajpal wrote: > >>We are given a 2-D array of 0s and 1s. >> We have to determine which row contains maximum no. of 1s in the array in >> O(m+n); >> where m - no. of rows and n - no. of columns. >> >> Sanju >> :) >> >> -- >> 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?hl=en. >> > > -- > 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?hl=en. > -- 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?hl=en.
Re: [algogeeks] Challenge
it is O(m+n). sure?? On Sat, Aug 20, 2011 at 2:52 PM, Sanjay Rajpal wrote: > We are given a 2-D array of 0s and 1s. > We have to determine which row contains maximum no. of 1s in the array in > O(m+n); > where m - no. of rows and n - no. of columns. > > Sanju > :) > > -- > 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?hl=en. > -- 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?hl=en.
[algogeeks] Challenge
We are given a 2-D array of 0s and 1s. We have to determine which row contains maximum no. of 1s in the array in O(m+n); where m - no. of rows and n - no. of columns. Sanju :) -- 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?hl=en.
