Skip to main content
1 of 3
gnasher729
  • 31.6k
  • 35
  • 55

It's really quite simple.

Step 1: Calculate the target sum, which is round (sum (x_i)). Let's say you get a value of 597.

Step 2: Calculate the sum that you get if you round every number down, that is sum (floor (x_i)). Let's say you get a value of 594.

Step 3: Calculate how many values must be rounded up. In this case, 597 - 594 = 3 x_i must be rounded up to get the required sum of 597.

Step 4: Determine which values to round up. You do this by finding (in this case) the three values where ceil (x_i) - x_i is largest.

Each of these steps is easily done in O (n) steps. So if you mentioned "subset-sum" problem to me and started to talk about NP and NP-complete, I'd be quite suspicious about your job application.

gnasher729
  • 31.6k
  • 35
  • 55