Kth sum in an array

Question

I have an array with n elements ,i need to calculate all n*n sum of pair of two elements (array[i]+array[j]).All sums are arranged in ascending order.I need to find Kth sum

for example:

array[] = {3,4,5}

all sums: {(3+3),(3+4),(4+3),(3+5),(5+3),(4+4),(4+5),(5+4),(5+5)}

K = 6

I need to find value for Kth sum ( in this case 6th sum is 4+4 ,i will return 8);

Solution might be very optimal

this is my solution; it isn't optimal:

for(i=0;i<n;i++)
    fin>>a[i];
qsort(a, n, sizeof(int), int_cmp);
for(i=0;i<n;i++)
    for(j=i;j<n;j++)
            {
                sum[k]=a[i]+a[j];
                if(i!=j)
                    sum[++k]=a[i]+a[j];
                k++;
                }
qsort(sum, n*n, sizeof(int), int_cmp);
cout<<sum[nrs-1];

i need an idea to implement this .I've implemented that ,but is inefficiently — Mike York, Mar 31 '15 at 23:33
If you posted the code maybe we could help you improve it. I don't know if anyone on this site will take the time to write it for you, although it doesn't seem very difficult. — DigitalNinja, Mar 31 '15 at 23:35
I solved that problem ,but inefficiently .I need an idea for that — Mike York, Mar 31 '15 at 23:35
i don't need an implemntation .I want an idea or an simple algorithm — Mike York, Mar 31 '15 at 23:36
I think I would start off by looping through the arrays and calculating the sums and putting the results into another array. Then sort the results array in ascending order. After that, it's easy to get the kth sum by just simply pointing to the kth element in the results array. — DigitalNinja, Mar 31 '15 at 23:40
this is same with my code :)) if i give an array with 10000 elements it's not working — Mike York, Mar 31 '15 at 23:43
Well that is the most direct approach. I suspected you probably did it that way ;) but you didn't say. — DigitalNinja, Mar 31 '15 at 23:45
Have you figured out which piece takes the longest? Have you tried `std::sort` instead? Could you run the operations (like more than one `qsort`, split up over the results array) in parallel? — DigitalNinja, Mar 31 '15 at 23:58
I don't tried std::sort 'cause I don't no to use STL ,and advanced C++, — Mike York, Apr 01 '15 at 00:06
i think this approaching isn't well. I want a new idea for that,seems like binary search — Mike York, Apr 01 '15 at 00:09

score 0 · Answer 1 · edited May 23 '17 at 12:22

I have seen a similar kind of question from google interview question in that they use two sorted array instead of one but the solution works.One optimization which will work in O(klogk) can be given here. To find the maximum value in such a case it is necessary to have calculated all the values lesser than it,ie let i,j be the maximum values in your case 5,5 to consider 5,5 to be max it is necessary to have evaluated both 4,5and 5,4.that is i-1,j and i,j-1 So a working code will be to use a heap in c++ it is a priority queue. The code is as follows

#include <iostream>  
#include <queue>  

using namespace std;   
for(i=0;i<n;i++)
fin>>a[i];
qsort(a, n, sizeof(int), int_cmp);
std::priority_queue<int > heap;


heap.add(pair(n-1, n-1));  // biggest pair n=array size

// remove max k-1 times 
for (int i = 0; i < k - 1; ++i) {
// get max and remove it from the heap
max = heap.pop();

// add next candidates
heap.push(pair(max.i - 1, max.j));
heap.push(pair(max.i, max.j - 1));
}

// get k-th maximum element
max = heap.pop();
maxVal = a[max.i] + a[max.j];

Now this one is optimized upto O(k.logk) there is another one which gives O(k).You can find it here.Kth sum in O(k)

Thanks a lot for this idea .But i still have a problem .I have some errors : 1) error: no type named 'value_type' in 'struct std::greater' 2)error: template argument 3 is invalid| I think i have to add a library or something — Mike York, Apr 01 '15 at 16:33
I have added the necessary modifications in the code. It is a thing about library or rather STL — anugrah nayar, Apr 01 '15 at 23:43

Kth sum in an array

1 Answers1