1058. Minimize Rounding Error to Meet Target

we have 2 options at each index so total complexity is 2^len(prices)? No, ceil = floor + 1 can be used to reduce the time complexity

ceil = floor + 1 so target - floorSum is the number of ceils we need
when using floor, error = x-floor(x); when using ceil, error = ceil - x = floor(x)+1-x = 1 - (x-floor(r)). So the cost flip floor to ceil is 1 - (x-floor(r)) + x-floor(x) = 1 - 2*(x-floor(x)). So we choose to maximize x-floor(x) when flipping

trap: we keep using ceil = floor + 1 but that's not true sometimes eg ceil(2.0) == floor(2.0). As a result, if not floorSum <= target <= ceilSum: != if not floorSum <= target <= floorSum+len(prices):

Will it happen that the price we select to flip doesn't increase the sum as expected? EG, ceil(2.0) == floor(2.0), namely floorError == 0.

for i in range(target - floorSum):
            errorSum += 1 - 2 * floorErrors[i]

If that happens, it means all following floorErrors are also 0, then there is no way we can reach target. This is not supposed to happen since we did "-1" check already, which guarantees that there is a valid solution.

class Solution:
    def minimizeError(self, prices: List[str], target: int) -> str:
        floorSum = 0
        ceilSum = 0
        errorSum = 0
        floorErrors = []
        for i, price in enumerate(prices):
            price = float(price)
            floorSum += math.floor(price)
            ceilSum += math.ceil(price)
            floorError = price - math.floor(price)
            errorSum += floorError
            floorErrors.append(floorError)
        
        if not floorSum <= target <= ceilSum:
            return "-1"
        
        floorErrors.sort(reverse=True)
        for i in range(target - floorSum):
            errorSum += 1 - 2 * floorErrors[i]
        return "{:.3f}".format(errorSum)

1058. Minimize Rounding Error to Meet Target - cocoder39/coco39_LC GitHub Wiki