Minimize Rounding Error to Meet Target - Practice Coding Problems

Minimize Rounding Error to Meet Target - Problem

Array Math String Greedy Sorting Medium

Given an array of prices [p1, p2, ..., pn] and a target, round each price pi to Roundi(pi) so that the rounded array [Round1(p1), Round2(p2), ..., Roundn(pn)] sums to the given target.

Each operation Roundi(pi) could be either Floor(pi) or Ceil(pi).

Return the string "-1" if the rounded array is impossible to sum to target. Otherwise, return the smallest rounding error, which is defined as Σ |Roundi(pi) - pi| for i from 1 to n, as a string with three places after the decimal.

Input & Output

Example 1 — Basic Case

$ Input: prices = [0.700,2.800,4.900], target = 8

› Output: "1.000"

💡 Note: Round to [1,3,5] to get sum=9>8. Round to [1,3,4] to get sum=8 with error |1-0.7|+|3-2.8|+|4-4.9|=0.3+0.2+0.9=1.4. But round to [0,3,5] gets sum=8 with error 0.7+0.2+0.1=1.0 which is better.

Example 2 — Impossible Case

$ Input: prices = [1.000,4.000,7.000], target = 20

› Output: "-1"

💡 Note: Maximum possible sum is 1+4+7=12, which is less than target 20, so it's impossible.

Example 3 — All Integers

$ Input: prices = [1.500,2.500,3.500], target = 6

› Output: "1.500"

💡 Note: Round to [1,2,3] gives sum=6. Error is |1-1.5|+|2-2.5|+|3-3.5|=0.5+0.5+0.5=1.5.

Constraints

1 ≤ prices.length ≤ 10⁴
0 ≤ prices[i] ≤ 10⁴
0 ≤ target ≤ 5 * 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of decimal prices and integer target sum

Process

Round each price up or down to minimize total error

Output

Minimum total rounding error as string with 3 decimal places

Key Takeaway

🎯 Key Insight: Round numbers with smaller fractional parts up first to minimize total rounding error

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a greedy approach: calculate feasibility bounds using floor/ceiling sums, then minimize error by rounding numbers with smallest fractional parts up first. Best approach is Greedy by Fractional Part: Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy by Fractional Part	O(n log n)	O(n)	Round based on fractional parts to minimize total error
Brute Force - Try All Combinations	O(2^n)	O(n)	Try all 2^n possible combinations of floor/ceil operations

Greedy by Fractional Part — Algorithm Steps

Calculate lower bound (all floors) and upper bound (all ceilings)
Check if target is achievable within bounds
Sort by fractional part and greedily round up smallest errors first

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Bounds

Find minimum (all floors) and maximum (all ceilings) possible sums

Sort by Fraction

Sort numbers by their fractional parts (ascending)

Greedy Selection

Round up numbers with smallest fractional parts first

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct {
    double fraction;
    int index;
} FractionalPart;

int compare(const void* a, const void* b) {
    FractionalPart* fa = (FractionalPart*)a;
    FractionalPart* fb = (FractionalPart*)b;
    if (fa->fraction < fb->fraction) return -1;
    if (fa->fraction > fb->fraction) return 1;
    return 0;
}

char* solution(double* prices, int n, int target) {
    int* floors = malloc(n * sizeof(int));
    int* ceilings = malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        floors[i] = (int)floor(prices[i]);
        ceilings[i] = (prices[i] == floors[i]) ? floors[i] : floors[i] + 1;
    }
    
    int lowerSum = 0, upperSum = 0;
    for (int i = 0; i < n; i++) {
        lowerSum += floors[i];
        upperSum += ceilings[i];
    }
    
    if (target < lowerSum || target > upperSum) {
        free(floors);
        free(ceilings);
        char* result = malloc(5);
        strcpy(result, "-1");
        return result;
    }
    
    int needToCeil = target - lowerSum;
    
    // Calculate fractional parts and sort by them
    FractionalPart* fractionalParts = malloc(n * sizeof(FractionalPart));
    for (int i = 0; i < n; i++) {
        fractionalParts[i].fraction = prices[i] - floors[i];
        fractionalParts[i].index = i;
    }
    
    qsort(fractionalParts, n, sizeof(FractionalPart), compare);
    
    double totalError = 0.0;
    
    // Round up the ones with smallest fractional parts first
    for (int i = 0; i < needToCeil; i++) {
        int idx = fractionalParts[i].index;
        totalError += ceilings[idx] - prices[idx]; // Error from ceiling
    }
    
    // Add error from remaining floors
    for (int i = needToCeil; i < n; i++) {
        int idx = fractionalParts[i].index;
        totalError += prices[idx] - floors[idx]; // Error from floor
    }
    
    char* result = malloc(20);
    sprintf(result, "%.3f", totalError);
    
    free(floors);
    free(ceilings);
    free(fractionalParts);
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    double prices[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[n++] = atof(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    char* result = solution(prices, n, target);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the fractional parts takes O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Additional arrays for fractional parts and indices

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

385 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy by Fractional Part — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler