@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.
