CareerCup

How about using max heap
1. take out the first K number, reverse it and save it in a heap H;
2. i=1 at first, compare A[i]+A[i+1] with the root of heap H[0], if lesser then abstract the maximum and insert the sum. loop until A[i]+A[i+1]>H[0].
3. i=1 at first,compare A[i]+A[i+1]+A[i+2] with the root of heap H[0], if lesser then abstract the maximum and insert the sum. loop until A[i]+A[i+1]+A[i+2]>H[0].
the first step cost O(K) while second and third step take O(KlogK).

int j=n-1, t = n-2, x = n-1, y = n-2, z = n-3;
    for(int i=n-1; i >= 1 && ind ;i--){

       // find pairs larger than the single element (i)
       for( ; j >= 1 && ind ;j--){
         for(; t>=0 && A[j]+A[t]>A[i];t--){

        // find triples larger than the pair (j,t)
           for(; x >= 2 && ind ;x--){
              for(; y>=1 && ind;y--){
                 for(; z>=0 && ind && A[x]+A[y]+A[z] > A[j]+ A[t] ;z--){
                   B[--ind] = A[x]+A[y]+A[z];
                 }
              }
           }
           
           // all triples larger than (j,t) are printed
           B[--ind] = A[j]+A[t];
    }
    // all pairs larger than (i) are printed
    B[--ind] = A[i];
}

It is O(k) because the loops continue from where they left...

a sample output:
array [] = {1,2,3,4,5}
number of smallest K = 16

1 = 1
2 = 2
3 = 1 + 2
3 = 3
4 = 1 + 3
4 = 4
5 = 2 + 3
5 = 1 + 4
5 = 5
6 = 1 + 2 + 3
6 = 1 + 5
6 = 2 + 4
7 = 1 + 2 + 4
7 = 2 + 5
7 = 3 + 4
8 = 1 + 3 + 4

Here's my solution using min heap that takes O(K log K) : ideone.com/BNIv7

Heap is initialized with smallest sum of 1, 2 and 3 elements, i.e. A[0], A[0]+A[1] and A[0]+A[1]+A[2]. Each sum keeps information of number of elements, and the indices of the elements. When the min sum in heap has one element, for example A[i], next element A[i+1] is inserted in Heap. For sum with 2 and 3 elements, the combinations of element need to be generated in a unique manner such that no two sum consisting of same indices can ever be generated. This is the hardest part of the solution. Try to work with previous posted example : {1,2,3,4,5} and K = 25.

I used verification to test my code with random input for N = 10, 20, 30, 40 and 50. Max. value of K was used to verify all possible combinations of sum. Hence for N = 50, K <= 50C3 + 50C2 + 50 = 20875. If you want to run with own input, please comment out line # 11.

<pre lang="" line="1" title="CodeMonkey90608" class="run-this">public class KBiggestElement {

private static int[] comPossiblities = new int[]{3, 5, 7};

public static void main(String[] args) {
int[] values = new int[]{1, 3, 5, 8, 16, 30, 35};
int cursor = 0;
int combinationCursor = 0;
int currentCombination = 0;

List<Integer> res = new ArrayList<Integer>(values.length);
for (int i = 0; i < values.length; i++) {
int combiValue = getCombiValue(values, combinationCursor, comPossiblities[currentCombination]);
if (combiValue < values[cursor]) {
res.add(combiValue);
currentCombination++;
if (currentCombination >= comPossiblities.length) {
currentCombination = 0;
combinationCursor++;
}
} else {
res.add(values[cursor++]);
}
}

System.out.println("res: " + res);


}

private static int getCombiValue(int[] values, int combinationCursor, int comPossiblity) {
int res = 0;
if (comPossiblity == 3) {
if (combinationCursor + 1 >= values.length) {
return Integer.MAX_VALUE;
}
res = values[combinationCursor] + values[combinationCursor + 1];
} else if (comPossiblity == 5) {
if (combinationCursor + 1 >= values.length) {
return Integer.MAX_VALUE;
}
res = values[combinationCursor] + values[combinationCursor + 2];
} else {
res = values[combinationCursor] + values[combinationCursor + 1] + values[combinationCursor+2];
}

return res;
}
}
</pre><pre title="CodeMonkey90608" input="yes">it's O(n) solution. No need for heap.

for every next smallest value, there are two possibilities, a single value or a combined value. For the combined the value, it has three possibilities 110, 101, 111.
So keep two cursors, one for the single value, one for the combined start value and move forwards.

Negatives need no special treatment.
</pre>

Maintain 3 vectors, the first one contains the element themselves, second one contains the sums of two, and the third one contains the sums of three, here's how to update these 3 vectors:

1. We get the numbers from the original array one by one.
2. It will first be appended to the first list
3. For each element in the first list, add the current number and append to second list
4. For each element in the second list, add the current number and append to third list

Now we have 3 sorted vector, we can just perform some lazy evaluation (extract the min of the first elements of each one) once we have extracted k numbers from the original array (when we can guarantee that the top k numbers we need are all in the 3 vectors).

int main() {
  int A[7] = {3,4,5,15,19,20,25};
  vector<int> original(A,A+7);
  vector<int> first;
  vector<int> second;
  vector<int> third;
  
  // now assume k = 7
  int k = 7;
  
  for (int i = 0; i < k; ++i) {
    for (int j = 0; j < second.size(); ++j)
      third.push_back(original[i]+second[j]);
    for (int j = 0; j < first.size(); ++j)
      second.push_back(original[i]+first[j]);
    first.push_back(original[i]);
  }

  vector<int> result;
  while (k > 0) {
    while (!first.empty() && first[0] <= second[0] && first[0] <= third[0] && k > 0) {
      result.push_back(first[0]);
      first.erase(first.begin());
      k--;
    }
    while (!second.empty() && second[0] < first[0] && second[0] <= third[0] && k > 0) {
      result.push_back(second[0]);
      second.erase(second.begin());
      k--;
    }    
    while (!third.empty() && third[0] < first[0] && third[0] < second[0] && k > 0) {
      result.push_back(third[0]);
      third.erase(third.begin());
      k--;
    }
  }

  k = result.size();
  for (int i = 0; i < k; ++i)
    cout << result[i] << " ";
  cout << endl;
  
  return 0;
}

I'm surprised to see how you claim your wrong code as correct. Your assumption is okay that k = size of array. See your program incorrect output for k = size of array = 20 here : ideone.com/WY3z6

One suggestion for you, before claiming your solution is correct or wrong, analyze it systematically. Thanks.

Note that your B array will be constructed from atmost p elements from A, p << k. You can bound p as follows: Say you choose the first p elements; they are guaranteed to be ordered. The total number of combinations of these p taking one, two or three at a time is pC1 + pC2 + pC3; this has to be bounded by k. So, go through p from 1 to k, and detect which p results in the sum being just greater than k; that's the p elements in B you are interested in. Now keep generating one at a time, two at a time and three at a time combinations from these p elements and put them into a min-heap; once you pull out k elements from the min-heap you are done. Time complexity? O(k) [for the initial test] + O(k'log k') [ where k' = pC1 + pC2 + pC3]; ideally k' would not be wildly different from k.

struct SumNode3{
	int i;
	int j;
	int k;
	int sum;
	int key;
	SumNode3(int* A, int i, int j, int k):i(i), j(j), k(k), sum(A[i] + A[j] + A[k]){
		key = A[i] + 100*A[j] + 10000*A[k];
	}
	SumNode3(int* A, int i, int j):i(i), j(j), k(-1), sum(A[i] + A[j]){
		key = A[i] + 100*A[j];
	}
	SumNode3(int* A, int i):i(i), j(-1), k(-1), sum(A[i]){
		key = A[i];
	}
};

vector<int> sortWithSum3(int*A, int n, int ksmall){
vector<SumNode3> sums;
sums.push_back(SumNode3(A, 0));
sums.push_back(SumNode3(A, 0, 1));
sums.push_back(SumNode3(A, 0, 1, 2));
unordered_set<int> set;
set.insert(sums[0].key);
set.insert(sums[1].key);
set.insert(sums[2].key);

vector<int> ret;
while(ksmall-- > 0 && !sums.empty())
{
int k = 0;

for(int j=1; j<sums.size(); j++)
{
if (sums[j].sum < sums[k].sum)
{
k = j;
}
}
ret.push_back(sums[k].sum);
cout<<sums[k].sum <<" i="<<sums[k].i<<" j="<<sums[k].j<<" k="<<sums[k].k<<endl;
if (sums[k].j == -1) // {1,2....}
{
if (sums[k].i < n-1)
{
sums[k] = SumNode3(A, sums[k].i+1);
set.insert(sums[k].key);
}
else
{
sums.erase(sums.begin()+k);
}
}
else if (sums[k].k == -1) // { sum(1,2) ....}
{
if (sums[k].i < n-2)
{
SumNode3 next(A, sums[k].i+1, sums[k].i+2);
if (set.find(next.key) == set.end())
{
sums.push_back(next);
set.insert(next.key);
}
}
if (sums[k].j < n-1)
{
sums[k] = SumNode3(A, sums[k].i, sums[k].j+1);
set.insert(sums[k].key);
}
else
{
sums.erase(sums.begin()+k);
}
}
else// { sum(1,2,3) ....}
{
if (sums[k].i < n-3)
{
SumNode3 next(A, sums[k].i+1, sums[k].i+2, sums[k].i+3);
if (set.find(next.key) == set.end())
{
sums.push_back(next);
set.insert(next.key);
}
}
if (sums[k].j < n-2)
{
SumNode3 next(A, sums[k].i, sums[k].j+1, sums[k].j+2);
if (set.find(next.key) == set.end())
{
sums.push_back(next);
set.insert(next.key);
}
}
if (sums[k].k < n-1)
{
sums[k] = SumNode3(A, sums[k].i, sums[k].j, sums[k].k+1);
set.insert(sums[k].key);
}
else
{
sums.erase(sums.begin()+k);
}
}
}
return ret;
}

Plz elaborate on the question.

Assuming all numbers are positive:

ind = k;
  for(int i=n-1; i >= 2 && ind ;i--){
     for(int j=i-1; j>=1 && ind;j--){
        for(int t=j-1; t>=0 && ind ;t--){
           B[--ind] = A[i]+A[j]+A[t];
        }
     }
  }
  if(ind){
    for(int i=n-1; i >= 1 && ind ;i--){
       for(int j=i-1; j>=0 && ind;j--){
           B[--ind] = A[i]+A[j];
       }
  }
  if(ind){
    for(int i=n-1; i >= 1 && ind ;i--){
           B[--ind] = A[i];
    }
  }

Please try to explain the problem better. Not able to understand the problem

Please try to explain the problem better. Not able to understand the problem