@Dave: He is talking of a better hash function. You did not mention the hash function which you will use.
Anuj Agarwal Engineering is the art of making what you want from things you can get. On Sat, May 21, 2011 at 9:59 AM, Dave <[email protected]> wrote: > @Apoorve: See my response at > http://groups.google.com/group/algogeeks/msg/72419fb69ce97774. > > Dave > > On May 20, 10:05 am, Apoorve Mohan <[email protected]> wrote: > > @dave: i think this can be handled using a good hash function(an onto > > function). then the space complexity will also be O(n). What say??? > > > > > > > > > > > > On Fri, May 20, 2011 at 8:31 PM, 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. > > > > -- > > regards > > > > Apoorve Mohan- 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. > > -- 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.
