can it be done in O(n) On Sun, Jun 12, 2011 at 11:00 PM, amit kumar <[email protected]>wrote:
> can it be done in O(nlogn) > > > On Sun, Jun 12, 2011 at 8:42 PM, Ashish Goel <[email protected]> wrote: > >> once the array is sorted, it is very easy >> have two pointers one on left and one on right take the sum, if sum is >> greater, move right one inwards else if less than sum, move left one inwards >> do this till sum is found of these two pointers meet >> >> >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> >> On Thu, Jun 9, 2011 at 11:04 AM, Amit Chauhan >> <[email protected]>wrote: >> >>> Hi, >>> >>> For x = 10,11,12,13.... it is going in infinite loop. >>> >>> Your recursive call for binary_search function is going in infinite loop. >>> So please look in to the logic for binary search function. >>> >>> And one more thing once you sort the array and after this you can search >>> the pair in linear time { for searching the element}. >>> >>> >>> ***Thanks and Regards >>> * >>> *Amit K Chauhan* >>> >>> >>> >>> * >>> ........................................................................................................ >>> There is always, always, always something to be thankful for !! >>> >>> ........................................................................................................ >>> * >>> >>> >>> >>> On Thu, Jun 9, 2011 at 10:57 AM, D.N.Vishwakarma@IITR <[email protected] >>> > wrote: >>> >>>> we have to find in O(nlgn) >>>> >>>> >>>> On Thu, Jun 9, 2011 at 10:55 AM, D.N.Vishwakarma@IITR < >>>> [email protected]> wrote: >>>> >>>>> #include<iostream> >>>>> using namespace std; >>>>> void merge(int A[],int p,int q,int r) >>>>> { >>>>> int n1=q-p+1;int n2=r-q; >>>>> int L[n1]; >>>>> int R[n2]; >>>>> for(int i=0;i<n1;i++) >>>>> L[i]=A[p+i]; >>>>> for(int j=0;j<n2;j++) >>>>> R[j]=A[q+j+1]; >>>>> int i=0,j=0,k; >>>>> >>>>> for(k=p;k<r;k++) >>>>> { >>>>> if((L[i]<=R[j])&&i<n1) >>>>> {A[k]=L[i];i++;} >>>>> else >>>>> {A[k]=R[j];j++;} >>>>> } >>>>> >>>>> for(;i<n1;i++) >>>>> {A[k]=L[i];k++;} >>>>> >>>>> for(;j<n2;j++) >>>>> {A[k]=R[j];k++;} >>>>> >>>>> } >>>>> >>>>> //Merge Sort >>>>> void merge_sort(int A[],int p,int r) >>>>> { >>>>> int q; >>>>> if(p<r) >>>>> { >>>>> q=(p+r)/2; >>>>> merge_sort(A,p,q); >>>>> merge_sort(A,q+1,r); >>>>> merge(A,p,q,r); >>>>> } >>>>> } >>>>> >>>>> //binary search >>>>> int binary_search(int A[],int left,int right,int val) >>>>> { >>>>> int result; >>>>> int mid=(left+right)/2; >>>>> if((right-left)==1&&val!=A[mid]) >>>>> result=-1; >>>>> if(val<A[mid]) >>>>> result=binary_search(A,left,mid-1,val); >>>>> else if(val>A[mid]) >>>>> result=binary_search(A,mid+1,right,val); >>>>> else >>>>> result= mid; >>>>> return result; >>>>> } >>>>> >>>>> >>>>> //main function >>>>> int main() >>>>> { >>>>> int A[]={3,2,4,6,5,7}; >>>>> merge_sort(A,0,5); >>>>> for(int i=0;i<6;i++) >>>>> cout<<A[i]<<" "; >>>>> cout<<endl; >>>>> int x; >>>>> cout<<"Enter value of x(=sum of two items in array)"<<endl; >>>>> cin>>x; >>>>> int pos;int flag=0;int i; >>>>> for( i=0;i<6;i++) >>>>> { >>>>> if((x-A[i])>0&&(pos=binary_search(A,i+1,5,x-A[i]))>=0) >>>>> {flag=1;break;} >>>>> } >>>>> if(flag) >>>>> { >>>>> cout<<"There are two whose sum is equal to given number"<<endl; >>>>> cout<<"Those numbers are "<<A[i]<<" and "<<A[pos]<<endl; >>>>> } >>>>> else >>>>> cout<<"There are no such two numbers"<<endl; >>>>> >>>>> return 0; >>>>> } >>>>> >>>>> >>>>> -- >>>>> **With Regards >>>>> Deoki Nandan Vishwakarma >>>>> IITR MCA >>>>> * >>>>> * >>>>> >>>>> >>>> >>>> >>>> -- >>>> **With Regards >>>> Deoki Nandan Vishwakarma >>>> IITR MCA >>>> * >>>> * >>>> >>>> -- >>>> 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. >>> >> >> -- >> 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.
