Problem statement

https://leetcode.com/problems/minimize-rounding-error-to-meet-target/

Solution

Let us have numbers $x_1, x_2, \dots, x_n$. Let us also denote $d_1, d_2, \dots, d_n$ their fraction parts. And by $s_1, s_2, \dots, s_n$ their integer parts. Then we need to have condition $s_1 + \dots + s_n <= target <= s_1 + \dots + s_n + n$ and if it is not holds, return -1.

Then we need to evaluate ceils is number of values we need to take ceil so in total we have sum target. We need to take target of them with ceil and n - ceils = k of them with floor. So, we need to minimuize $q_1 + \dots + q_k + (1-q_{k+1} + \dots + 1 - q_n)$, where $q_i$ is some permutation of $d_i$. It can be rewritten as $q_1 + \dots + q_n + (1-2q_{k+1} + \dots + 1-2q_{n})$. First part is constant, we need to minimize the second one, so we need to take biggest n-k = ceils values and ceils of them and take k smallest values and take floors of them.

Complexity

Time complexity is O(n log n), space complexity is O(n)

Code

class Solution:
    def minimizeError(self, prices, target):
        diff = []
        low, high = 0, 0
        for i, p in enumerate(map(float, prices)):
            f = floor(p)
            low += f
            x = p - f
            high += f + (x!= 0)
            if x != 0:
                diff.append((x, 1-x))

        if not low <= target <= high:
            return "-1"

        diff = sorted(diff)[::-1]
        ceils = target - low
        return "{:.3f}".format(sum([d[1] for d in diff[:ceils]]) + sum([d[0] for d in diff[ceils:]]))