actly i did.. but bhavana didn;t used STL ..!! My question to you was regarding Dave 's query which i didn't understand what he meant by saying : "@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? "
On Fri, May 27, 2011 at 2:44 PM, Aakash Johari <[email protected]>wrote: > @sukhmeet: could you get my approach? it was same as Bhavana explained. > > On Fri, May 27, 2011 at 2:12 AM, bhavana <[email protected]> wrote: > >> hehe...d difference is regarding time complexity...bcoz map takes 0(logN) >> for insertion while array can b accessed in constant time through index. >> >> >> On Fri, May 27, 2011 at 2:39 PM, sukhmeet singh >> <[email protected]>wrote: >> >>> 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 <[email protected]> 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 <[email protected]> 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 < >>>>> [email protected]> 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 <[email protected]>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 < >>>>>>> [email protected]> 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 < >>>>>>>> [email protected]> 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 < >>>>>>>>> [email protected]> 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 <[email protected]>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 <[email protected]> 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 <[email protected]> >>>>>>>>>>> wrote: >>>>>>>>>>> > > @Aakash: Yeah, but try the same array with sum = 6 and see >>>>>>>>>>> what >>>>>>>>>>> > > happens. >>>>>>>>>>> > >>>>>>>>>>> > > Dave >>>>>>>>>>> > >>>>>>>>>>> > > On May 20, 9:04 am, Aakash Johari <[email protected]> >>>>>>>>>>> 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 < >>>>>>>>>>> [email protected]> wrote: >>>>>>>>>>> > > > > We can sort using STL sort function in main() before >>>>>>>>>>> function call of >>>>>>>>>>> > > > > arraysum(). >>>>>>>>>>> > >>>>>>>>>>> > > > > On May 20, 6:49 am, Gunjan Sharma < >>>>>>>>>>> [email protected]> 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 < >>>>>>>>>>> [email protected]> 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 <[email protected]> >>>>>>>>>>> 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 >>>>>>>>>>> [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. >>>>>>>>>>> > >>>>>>>>>>> > > > > > -- >>>>>>>>>>> > > > > > 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 >>>>>>>>>>> [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. >>>>>>>>>>> > >>>>>>>>>>> > > > -- >>>>>>>>>>> > > > -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 >>>>>>>>>>> [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. >>>>>>>>>>> > >>>>>>>>>>> > -- >>>>>>>>>>> > -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 [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. >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> -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 [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. >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> -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 [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. >>>> >>> >>> -- >>> 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. >> > > > > -- > -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 [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.
