Dear Piyush Sinha, On Tue, Jun 7, 2011 at 10:57 PM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote:
> it will definitely give wrong results... In what way, the result given by the algorithm for the sequence is "wrong"? And moreover, the question was asked to output two integers such that their difference is 'k'. It was not asked to find all the pairs. Anyway, you should have noticed that finding all pairs can also be done by just incrementing the second pointer when there is a match, if you had tried to understand the algorithm. > > try for -3 -2 -1 0 1 2 4 5 7 > > and search for 6 using ur algo > > On 6/7/11, Shivaji Varma <shivaji...@gmail.com> wrote: > > How about this? > > > > Take two pointers, one pointing to the first element in the array and > second > > one pointing to second element in the array. If the difference is less > than > > 'k', increment the second pointer and if the difference is greater, > > increment the first pointer. And if pointer 1 exceeds pointer 2, then the > > search pair (a,b) doesn't exist. > > > > On Tue, Jun 7, 2011 at 3:20 PM, ross <jagadish1...@gmail.com> wrote: > > > >> @piyush: > >> in the case of a+b=k, > >> assuming a and b are 2 ptrs to start and end, > >> when u increase a, sum increases and when u decrease b > >> sum decreases. i doubt if that s the same case for a-b.. > >> > >> On Jun 7, 2:47 pm, ross <jagadish1...@gmail.com> wrote: > >> > Can u use the same logic u use for a+b=k for difference.. > >> > because, here if you increase a or decrease b in both case > >> > difference will increase.. ? correct me if i am wrong. > >> > > >> > On Jun 7, 2:39 pm, Piyush Sinha <ecstasy.piy...@gmail.com> wrote: > >> > > >> > > >> > > >> > > >> > > >> > > >> > > >> > > Whats the problem in using two pointers one pointing the lower index > >> while > >> > > the other pointing the upper index?? > >> > > >> > > On Tue, Jun 7, 2011 at 2:57 PM, ross <jagadish1...@gmail.com> > wrote: > >> > > > Given an integer 'k' and an sorted array A (can consist of both > >> > > > +ve/- > >> > > > ve nos), > >> > > > output 2 integers from A such that a-b=k. > >> > > > PS: > >> > > > nlogn solution would be to check for the occurence of k-a[i] > (using > >> > > > bin search) when you > >> > > > encounter a[i]. methods like hash consume space. > >> > > >> > > > Is an O(n) solution with O(1) extraspace possible? > >> > > >> > > > -- > >> > > > 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. > >> > > >> > > -- > >> > > *Piyush Sinha* > >> > > *IIIT, Allahabad* > >> > > *+91-8792136657* > >> > > *+91-7483122727* > >> > > *https://www.facebook.com/profile.php?id=100000655377926* > >> > >> -- > >> 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. > > > > > > > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-8792136657* > *+91-7483122727* > *https://www.facebook.com/profile.php?id=100000655377926 * > > -- > 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.
