can we calculate all a,b pairs in an sorted array where (a + b = k) in O(n). can we calculate all a,b pairs in an sorted array where (a - b = k) in O(n).
On Wed, Jun 8, 2011 at 10:24 AM, Piyush Sinha <[email protected]>wrote: > wat about (5,-1),(1,7)......[?][?] > > > On Wed, Jun 8, 2011 at 8:45 AM, Shivaji Varma <[email protected]>wrote: > >> If I do the search for 6 in the sequence that you gave, the output will be >> 4 and -2. The difference between them is 6. Whats wrong in this??? >> >> >> On Tue, Jun 7, 2011 at 10:57 PM, Piyush Sinha >> <[email protected]>wrote: >> >>> it will definitely give wrong results... >>> >>> try for -3 -2 -1 0 1 2 4 5 7 >>> >>> and search for 6 using ur algo >>> >>> On 6/7/11, Shivaji Varma <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> >>> 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 [email protected] >>> . >>> >> > > > To unsubscribe from this group, send email to >>> >> > > > [email protected]. >>> >> > > > 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 [email protected]. >>> >> To unsubscribe from this group, send email to >>> >> [email protected]. >>> >> 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 [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]. >>> > 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: [email protected] Another Email :: [email protected] People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<329.gif>>
