1. use radix sort and sort the array. 2. take two pointers(say i and j). Point the first to head and the second to the tail of the array. then check for a[i] + a[j]. If this sum is greater the decrement the pointer j else if the sum is less than k increment the i pointer. If you get the sum equal to k then stop else move untill j > i.
I think this solution will have O(n) time complexity and O(n space complexity). On Fri, May 20, 2011 at 7:22 PM, Aakash Johari <aakashj....@gmail.com>wrote: > One possible solution is using maps. But i think that won't be in O(n) > > > On Fri, May 20, 2011 at 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) > > > > > -- > 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 Apoorve Mohan -- 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.