You are given an array A of k values which contain int values in sorted (asec) order. Find top k values (asec) which can either be the number from the array A, or sum of any two numbers from A or sum of any three numbers from A. So, if A's values are represented as : a1,a2,...,ak , the possible numbers can be: a(i), a(i)+a(j), a(i)+a(j)+a(l) for any i,j,l < k

Ex: A[7] = {3,4,5,15,19,20,25}

output B[7] = {3,4,5,(3+4),(3+5),(4+5),(3+4+5)}

create a min-heap out of array A,

now get the root, ie 3, and do min-heapify.

after that again get the root ie 4, add it to the rest of the elements seen so far and push back on min-heap.

so in output we have 3, 4

heap we have 5, 7, 15, 19, 20, 25

get the root, add it to each element of the outpu array and push the result back on heap.

also take 2 elements at a time from the array and add it to 5 and push back the result on min-heap and heapify.

output we have now, 3, 4, 5

pushing on heap - (3+5), (4+5) (3+4+5)

heap is now: 7, 8, 9, 12, 15, 19, 20, 25

again get the root and do the above steps,

finally we will have the output array as:

3, 4, 5, 7, 8, 9, 12

Total time complexity:

klogk + k^2

## No comments:

Post a Comment