Monday, March 26, 2012

Find top k from given array.


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