< Back to forum


I am unable to solve the question in the above link 

Asked by: Proma_Roy on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Enter your answer details below:


Enter your comment details below:


1 Answer(s)


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.

Samrat_De last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.