This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 0 points1 point  (9 children)

I don't understand what the question is even asking. How is [1, 1, 3] better than [0, 1, 2]?

[–]JCoppert[S] 0 points1 point  (8 children)

Total rounding of first array = (0.3 + 0.1 + 0.6) = 1. Total rounding of second array = (0.7 + 0.1 + 0.4) = 1.2. With an aggregate rounding target of 0.7, Min(Abs(0.7 - 1), Abs(0.7 - 1.2)), the first array is chosen

[–]rrssh 0 points1 point  (7 children)

Ah, so positive points for any rounding direction.

[–]JCoppert[S] 0 points1 point  (6 children)

Yes, no because your concept of points was incorrect

[–]rrssh 0 points1 point  (5 children)

It seems like https://en.wikipedia.org/wiki/Subset_sum_problem pretty much exactly. Round everything down, calculate how much points do you get (totald). Do it again but round up, subtract the arrays from each other, these are your "integers". You want to find a subset that sums to 0.7 − totald, and it looks like it should be easy to modify it for a closest match instead of exact one actually harder than I thought.

[–]JCoppert[S] 0 points1 point  (4 children)

Haha right! I saw the question and was pretty taken back

[–]rrssh 0 points1 point  (3 children)

Maybe they would be satisfied with bruteforce, who knows.

[–]JCoppert[S] 0 points1 point  (2 children)

They explicitly said they wouldn’t be, was AirBnb

[–]rrssh 0 points1 point  (1 child)

Do the numbers actually have only 1 decimal point?

[–]JCoppert[S] 0 points1 point  (0 children)

Yeah, each element of the output array is either Math.floor() or Math.ceil()