k.. got it .. but it was same as putting them into a map ..if the bound 'b' is not known.. as said be Akash .. But if STL is not allowed your approach is mch better..Noogle..
also a simple change that can be done if the each number is that we can check if (sum - a[i] )!= i then getting same can be avoided On Fri, May 27, 2011 at 2:32 PM, bhavana <bhavana....@gmail.com> wrote: > hey...bt this one works only in case given that the elements of the array > are non-negative. > > > On Fri, May 27, 2011 at 2:30 PM, bhavana <bhavana....@gmail.com> wrote: > >> @sukhi : instead of using a map...use a boolean array elements of whoch r >> initialised to false. >> >> Starting frm the first element of the array....if the number n is greater >> than k ignore it....else mark a[n]=true and check if a[k-n]==true then we >> get the required result .....bt if we reach the end of array without >> entering the if condition the array doesnt contain any such pair. >> >> >> On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh >> <sukhmeet2...@gmail.com>wrote: >> >>> @bhavana : Explain..!! >>> as far as i get you is that it would be same as implementing map ...!! >>> isn't ?? >>> >>> >>> On Fri, May 27, 2011 at 2:16 PM, bhavana <bhavana....@gmail.com> wrote: >>> >>>> can be solved easily if the elements of the array lie in a limited range >>>> which can b known beforehand...!! >>>> >>>> >>>> On Fri, May 27, 2011 at 2:10 PM, Aakash Johari >>>> <aakashj....@gmail.com>wrote: >>>> >>>>> yes, you are right. map insertion takes O(log n) time. so if you know >>>>> the upper bound of N, you can simply map the existence/non-existence of >>>>> any >>>>> particular element in an array. that will be in constant time (for query >>>>> purposes) and O(n) time for preprocessing. >>>>> >>>>> >>>>> On Fri, May 27, 2011 at 1:29 AM, sukhmeet singh < >>>>> sukhmeet2...@gmail.com> wrote: >>>>> >>>>>> @Dave nd @Akash can u explain a bit more.. I didn't get what u say.. >>>>>> Inserting in a map takes O(log n) time !! >>>>>> >>>>>> On Fri, May 20, 2011 at 8:35 PM, Aakash Johari <aakashj....@gmail.com >>>>>> > wrote: >>>>>> >>>>>>> @Dave: This is what is still a doubt to me. I have searched but >>>>>>> couldn't get the info regarding this. >>>>>>> >>>>>>> >>>>>>> On Fri, May 20, 2011 at 8:01 AM, Dave <dave_and_da...@juno.com>wrote: >>>>>>> >>>>>>>> @Aakash: And tell me how map works. Is making an entry O(1) >>>>>>>> regardless >>>>>>>> of the value of the entry? For example, is it O(n) to map the >>>>>>>> sequence >>>>>>>> 1, 4, 9, 16, 25, ..., n^2? >>>>>>>> >>>>>>>> Dave >>>>>>>> >>>>>>>> On May 20, 9:39 am, Aakash Johari <aakashj....@gmail.com> wrote: >>>>>>>> > @Dave: I got you. I will have to check before pushing the element >>>>>>>> in map. >>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> > On Fri, May 20, 2011 at 7:30 AM, Dave <dave_and_da...@juno.com> >>>>>>>> wrote: >>>>>>>> > > @Aakash: Yeah, but try the same array with sum = 6 and see what >>>>>>>> > > happens. >>>>>>>> > >>>>>>>> > > Dave >>>>>>>> > >>>>>>>> > > On May 20, 9:04 am, Aakash Johari <aakashj....@gmail.com> >>>>>>>> wrote: >>>>>>>> > > > int main() >>>>>>>> > > > { >>>>>>>> > > > int a[10] = {5, 3, 10, 9, 8, 23, 11, 4, 12, 6}; >>>>>>>> > > > int i; >>>>>>>> > > > int sum; >>>>>>>> > > > int flag = 0; >>>>>>>> > >>>>>>>> > > > map<int, int> m; >>>>>>>> > >>>>>>>> > > > for ( i = 0; i < 10; i++ ) { >>>>>>>> > > > m[a[i]] = 1; >>>>>>>> > > > } >>>>>>>> > >>>>>>>> > > > sum = 13; >>>>>>>> > >>>>>>>> > > > for ( i = 0; i < 10; i++ ) { >>>>>>>> > > > if ( m[sum - a[i]] == 1 ) { >>>>>>>> > > > flag = 1; >>>>>>>> > > > break; >>>>>>>> > > > } >>>>>>>> > > > } >>>>>>>> > >>>>>>>> > > > if ( flag == 1 ) >>>>>>>> > > > cout << a[i] << " " << sum - a[i] << endl; >>>>>>>> > >>>>>>>> > > > return 0; >>>>>>>> > >>>>>>>> > > > } >>>>>>>> > > > On Fri, May 20, 2011 at 7:01 AM, hari <rajakin...@gmail.com> >>>>>>>> wrote: >>>>>>>> > > > > We can sort using STL sort function in main() before >>>>>>>> function call of >>>>>>>> > > > > arraysum(). >>>>>>>> > >>>>>>>> > > > > On May 20, 6:49 am, Gunjan Sharma <gunjan.khan...@gmail.com> >>>>>>>> wrote: >>>>>>>> > > > > > First of all there is an infinite loop in this code.... >>>>>>>> > > > > > Secondly it works only for sorted array. >>>>>>>> > >>>>>>>> > > > > > On Fri, May 20, 2011 at 7:16 PM, hari < >>>>>>>> rajakin...@gmail.com> wrote: >>>>>>>> > > > > > > In while loop have i,j which points first and last index >>>>>>>> of array. >>>>>>>> > > In >>>>>>>> > > > > > > while loop, Check the sum of a[i],a[j], If >>>>>>>> sum<k,increment i or >>>>>>>> > > else >>>>>>>> > > > > > > decrement j. Run the while loop till i<j.. >>>>>>>> > >>>>>>>> > > > > > > CODE: >>>>>>>> > >>>>>>>> > > > > > > int arraysum(int a[], int k, int i, int j) >>>>>>>> > > > > > > while(i<j) >>>>>>>> > > > > > > { >>>>>>>> > > > > > > int p=0; >>>>>>>> > > > > > > int b[10]; //to store index of selected nos >>>>>>>> > > > > > > sum=a[i]+a[j]; >>>>>>>> > > > > > > if (sum==k) >>>>>>>> > > > > > > { >>>>>>>> > > > > > > b[p++]=i;b[p++]=j; >>>>>>>> > > > > > > } >>>>>>>> > > > > > > elseif(sum<k) >>>>>>>> > > > > > > i++; >>>>>>>> > > > > > > else(sum>k) >>>>>>>> > > > > > > j++; >>>>>>>> > > > > > > return b; >>>>>>>> > > > > > > } >>>>>>>> > >>>>>>>> > > > > > > On May 20, 4:38 am, amit <amitthecoo...@gmail.com> >>>>>>>> wrote: >>>>>>>> > > > > > > > given an array of integers, and an integer k, find out >>>>>>>> two >>>>>>>> > > elements >>>>>>>> > > > > > > > from the array whose sum is k in O(n) time. if no such >>>>>>>> element >>>>>>>> > > exists >>>>>>>> > > > > > > > output none. >>>>>>>> > >>>>>>>> > > > > > > -- >>>>>>>> > > > > > > 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. >>>>>>>> > >>>>>>>> > > > > > -- >>>>>>>> > > > > > Regards >>>>>>>> > > > > > Gunjan Sharma >>>>>>>> > > > > > B.Tech IV year CSE >>>>>>>> > >>>>>>>> > > > > > Contact No- +91 9997767077 >>>>>>>> > >>>>>>>> > > > > -- >>>>>>>> > > > > 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. >>>>>>>> > >>>>>>>> > > > -- >>>>>>>> > > > -Aakash Johari >>>>>>>> > > > (IIIT Allahabad)- Hide quoted text - >>>>>>>> > >>>>>>>> > > > - Show quoted text - >>>>>>>> > >>>>>>>> > > -- >>>>>>>> > > 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. >>>>>>>> > >>>>>>>> > -- >>>>>>>> > -Aakash Johari >>>>>>>> > (IIIT Allahabad)- Hide quoted text - >>>>>>>> > >>>>>>>> > - Show quoted text - >>>>>>>> >>>>>>>> -- >>>>>>>> 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. >>>>>>>> >>>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> -Aakash Johari >>>>>>> (IIIT Allahabad) >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> -Aakash Johari >>>>> (IIIT Allahabad) >>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> 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. > -- 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.