Calculating the Kth sum

Question

My problem goes like this: I have a number N <= 50000 and an array A with N elements. The values in A are positive numbers ranging from 0 to 2^21. I need to compute all the sums A[i] + A[j] where 0 <= i, j < N (i can be equal to j so A[1] + A[1] is a valid sum). I then need to sort ascending the sums and retrieve the Kth sum (where K is a given value).

Example:

N = 3
K = 4
A = [7, 2, 5]

The following sums come up:

The Kth sum is the 4th : 2 + 7 = 9

Ideally i want the complexity to be O(n * log n) so i would like to avoid the brute method of calculating all sums, sorting them and retrieving the Kth value.

The first thing i did was to sort the array, i used merge sort for this.

However, i am not really sure how to proceed further, which algorithm would be better suited for my task.

It is a bit tricky from my point of view, i made a little something which worked for some values but when i tried it for more numbers (e.g. 20) it started to fail. Therefore probably my solution is not what i should do here.

Below you can see what i did so far (without the sorting, i just hardcoded a sorted array in the code):

import java.util.*;

public class KthSum {
    public static void main(String args[]) {
        Integer numbersCount = 3;

        ArrayList<Integer> sortedList = new ArrayList<Integer>();
        sortedList.add(2);
        sortedList.add(5);
        sortedList.add(7);
        sortedList.add(9);
        sortedList.add(10);
        sortedList.add(13);
        sortedList.add(14);
        sortedList.add(16);
        sortedList.add(17);
        sortedList.add(20);
        sortedList.add(21);
        sortedList.add(26);
        sortedList.add(32);
        sortedList.add(33);
        sortedList.add(34);
        sortedList.add(41);

        Integer desiredSumIndex = 153;

        Integer i = 0,
                j = 0,
                sumIndex = 0;

        while (sumIndex < desiredSumIndex) {
            Integer sum1 = 0;
            Integer sum2 = 0;
            if (i == j) {
                sumIndex++;
                if (sumIndex >= desiredSumIndex) break;
                j++;
            } else {
                sumIndex++;
                if (sumIndex >= desiredSumIndex) break;
                sumIndex++;
                if (sumIndex >= desiredSumIndex) {
                    Integer k = i;
                    i = j;
                    j = k;
                    break;
                }
                sum1 = i < numbersCount - 1 ? sortedList.get(i + 1) * 2 : 0;
                sum2 = j < numbersCount - 1 ? sortedList.get(i) + sortedList.get(j + 1) : sum1 + 1;

                if (sum1 < sum2) {
                    i++;
                    j = i;
                } else {
                    j++;
                }
            }
        }

        Integer outputSum = sortedList.get(i) + sortedList.get(j);

        System.out.println(String.format("The sum is %d and it is composed from the positions %d and %d", outputSum, i, j));
    }
}

I need any help i can get. All ideas welcomed :)

Cheers, Alex

Hint: In linear time, can you check whether a given value is bigger than the kth pair sum? — tmyklebu, Apr 04 '15 at 20:53
Several of the questions on the "related" list are more or less exact duplicates of this. A variation of this problem has been called a Google interview question, and another version has been asked on a competitive programming site. See http://stackoverflow.com/questions/18557175/how-to-find-pair-with-kth-largest-sum and http://stackoverflow.com/questions/1436669/how-to-find-kth-largest-number-in-pairwise-sums-like-seta-setb. — Douglas Zare, Apr 05 '15 at 01:49

Calculating the Kth sum

0 Answers0