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 <[email protected]>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 > <[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) > > > > > -- > 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 -- 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.
