I am unable to solve the question in the above link 

Proma Roy

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load

Please make sure the answer is not too short

1 Answer

Samrat 10:32, Oct 28
Samrat De

As the subset sum can be greater than or equal to x, first we have to sort the array in decreasing order, then do a prefix sum in another array, say of name, ptr[].

Then store the elements of the ptr in the map(say of name, m), with the ptr elements as 'key' and index (use 1 based indexing) of that element as 'value'.

Then for each query do a lower bound search for x in the map, and print the 'value' of the element which is found. If the search results in m.end(), then print(-1).

Btw, Lower Bound search means searching in the map, till an element greater than or equal to x is encountered.

Be careful, you don't have to print answer for each query, but for each test case as whole.

Please make sure the answer is not too short
No Comments yet