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.

You would get bonus points if you talked about rounding errors and how to make sure that round (sum (x_i)) is calculated correctly in the face of rounding errors. Or if you improved the speed and reduced rounding errors by combining my Step 1 and Step 2 into one.

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.

You would get bonus points if you talked about rounding errors and how to make sure that round (sum (x_i)) is calculated correctly in the face of rounding errors. Or if you improved the speed and reduced rounding errors by combining my Step 1 and Step 2 into one (that's what nir shahar's solution does).

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.

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.

You would get bonus points if you talked about rounding errors and how to make sure that round (sum (x_i)) is calculated correctly in the face of rounding errors. Or if you improved the speed and reduced rounding errors by combining my Step 1 and Step 2 into one.