You are not logged in. Please login at to post your questions!


GOODS - Editorial



Author: Jatin Gupta
Tester: Aanya Jindal
Editorialist: Naman Goyal






In problem statement, it is given that there are n(even) number of people and we have to do pairing of them in such a manner that the sum of the numbers assigned to them should be greater than k.


After sorting the laddus, we take last and first element. If they form a valid pair, then we take the next minimum and next maximum laddus. Else, we advance the minimum and add 1 to the unsatisfied number of people.(As the minimum cant form valid pair with any other remaining person).


We have to minimise the number of people left who can not reach the given amount(k).

We see how we can use the greedy strategy to solve the given problem.

If the sum of laddus of 2 people is greater than k, then it does not matter how much greater than k they have.

So we try to pair the person with maximum laddus with the person having minimum laddus. If they are not able to form a valid pair, then the person having minimum laddus cannot form a valid pair with anyone else. So, we add that person to the list of people who can't be in any pair.

(Let’s say we use an array as our data structure, then sorting gives an ordered arrangement of the elements in ascending manner.)

To minimize the number of people left we need to take the minimum and maximum amount of the array and then check whether their sum is greater than k or not.

If yes, then move on to the next minimum and maximum number and repeat the process until we reach the point where minimum and maximum become same or minimum become greater than maximum.

If no, then check for the next minimum number keeping the maximum number same and repeat the checking process until we reach the point where minimum and maximum become same or minimum become greater than maximum.


Author's solution can be found here.
Tester's solution can be found here.

asked 24 Apr '18, 13:05

jatin_cpp's gravatar image

accept rate: 0%

edited 26 Apr '18, 16:41

admin's gravatar image

0★admin ♦♦

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 24 Apr '18, 13:05

question was seen: 187 times

last updated: 26 Apr '18, 16:41