Problem

You are given an array X of floating-point numbers x1, x2, ... xn. These can be rounded up or down to create a corresponding array Y of integers y1, y2, ... yn.

Write an algorithm that finds an appropriate Y array with the following properties:

  • The rounded sums of both arrays should be equal.
  • The absolute pairwise difference between elements is minimized. In other words, |x1- y1| + |x2- y2| + ... + |xn- yn| should be as small as possible.

For example, suppose your input is [1.3, 2.3, 4.4]. In this case you cannot do better than [1, 2, 5], which has an absolute difference of |1.3 - 1| + |2.3 - 2| + |4.4 - 5| = 1.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: X = [1.3, 2.3, 4.4]
Output: Y = [1, 2, 5]
Explanation:
Target sum = round(1.3 + 2.3 + 4.4) = round(8.0) = 8
Sum of floors = floor(1.3) + floor(2.3) + floor(4.4) = 1 + 2 + 4 = 7
Need to round up 1 element to reach target sum 8
Choose 4.4 -> 5 (difference = 0.6) over others for minimal total difference
Total difference = |1.3-1| + |2.3-2| + |4.4-5| = 0.3 + 0.3 + 0.6 = 1.2

Example 2

1
2
3
4
5
6
7
8

Input: X = [2.5, 3.5, 1.0]
Output: Y = [2, 4, 1] or Y = [3, 3, 1]
Explanation:
Target sum = round(2.5 + 3.5 + 1.0) = round(7.0) = 7
Sum of floors = floor(2.5) + floor(3.5) + floor(1.0) = 2 + 3 + 1 = 6
Need to round up 1 element to reach target sum 7
Both 2.5->3 and 3.5->4 have same fractional part (0.5), so either choice gives optimal result
Total difference = 0.5 + 0.5 + 0.0 = 1.0

Example 3

1
2
3
4
5
6
7
8
9

Input: X = [1.1, 1.9, 2.8, 3.2]
Output: Y = [1, 2, 3, 3]
Explanation:
Target sum = round(1.1 + 1.9 + 2.8 + 3.2) = round(9.0) = 9
Sum of floors = floor(1.1) + floor(1.9) + floor(2.8) + floor(3.2) = 1 + 1 + 2 + 3 = 7
Need to round up 2 elements to reach target sum 9
Choose elements with largest fractional parts: 1.9 (0.9) and 2.8 (0.8)
Result: [1, 2, 3, 3]
Total difference = |1.1-1| + |1.9-2| + |2.8-3| + |3.2-3| = 0.1 + 0.1 + 0.2 + 0.2 = 0.6

Example 4

1
2
3
4
5
6
7
8
9

Input: X = [3.7, 2.1, 1.9, 4.3]
Output: Y = [4, 2, 2, 4]
Explanation:
Target sum = round(3.7 + 2.1 + 1.9 + 4.3) = round(12.0) = 12
Sum of floors = floor(3.7) + floor(2.1) + floor(1.9) + floor(4.3) = 3 + 2 + 1 + 4 = 10
Need to round up 2 elements to reach target sum 12
Choose elements with largest fractional parts: 3.7 (0.7) and 4.3 (0.3)
Result: [4, 2, 2, 4]
Total difference = |3.7-4| + |2.1-2| + |1.9-2| + |4.3-4| = 0.3 + 0.1 + 0.1 + 0.3 = 0.8

Example 5

1
2
3
4
5
6
7

Input: X = [1.0, 2.0, 3.0]
Output: Y = [1, 2, 3]
Explanation:
Target sum = round(1.0 + 2.0 + 3.0) = round(6.0) = 6
Sum of floors = floor(1.0) + floor(2.0) + floor(3.0) = 1 + 2 + 3 = 6
No rounding up needed since target sum already achieved
Total difference = |1.0-1| + |2.0-2| + |3.0-3| = 0.0 + 0.0 + 0.0 = 0.0

Solution

Method 1 - Greedy Fractional Part Selection

Intuition

To minimize the total absolute difference while preserving the rounded sum, we should floor all numbers initially (which minimizes individual differences), then selectively round up elements with the largest fractional parts. The key insight is that rounding up an element with fractional part f costs exactly 1-f in additional difference, so we want to minimize this cost.

Approach

  1. Calculate the target sum by rounding the sum of all elements in the input array
  2. Initialize result array by flooring all input elements
  3. Calculate current sum of floored elements
  4. Determine how many elements need to be rounded up to reach target sum
  5. Create array of (fractional_part, index) pairs and sort by fractional part in descending order
  6. Round up the elements with largest fractional parts until target sum is reached
  7. Return the resulting integer array

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
public:
    vector<int> optimalRounding(vector<double>& X) {
        int n = X.size();
        vector<int> Y(n);
        
        // Calculate target sum (rounded sum of original array)
        double totalSum = 0;
        for (double x : X) {
            totalSum += x;
        }
        int targetSum = (int)round(totalSum);
        
        // Initialize with floor values and calculate current sum
        int currentSum = 0;
        for (int i = 0; i < n; i++) {
            Y[i] = (int)floor(X[i]);
            currentSum += Y[i];
        }
        
        // Calculate how many elements need to be rounded up
        int roundUpCount = targetSum - currentSum;
        
        // Create pairs of (fractional_part, index) and sort by fractional part
        vector<pair<double, int>> fractionalParts;
        for (int i = 0; i < n; i++) {
            double fractionalPart = X[i] - floor(X[i]);
            fractionalParts.push_back({fractionalPart, i});
        }
        
        // Sort by fractional part in descending order
        sort(fractionalParts.begin(), fractionalParts.end(), greater<pair<double, int>>());
        
        // Round up the elements with largest fractional parts
        for (int i = 0; i < roundUpCount; i++) {
            int idx = fractionalParts[i].second;
            Y[idx]++;
        }
        
        return Y;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

func optimalRounding(X []float64) []int {
    n := len(X)
    Y := make([]int, n)
    
    // Calculate target sum (rounded sum of original array)
    totalSum := 0.0
    for _, x := range X {
        totalSum += x
    }
    targetSum := int(math.Round(totalSum))
    
    // Initialize with floor values and calculate current sum
    currentSum := 0
    for i, x := range X {
        Y[i] = int(math.Floor(x))
        currentSum += Y[i]
    }
    
    // Calculate how many elements need to be rounded up
    roundUpCount := targetSum - currentSum
    
    // Create pairs of (fractional_part, index)
    type FractionalPair struct {
        fractionalPart float64
        index         int
    }
    
    fractionalParts := make([]FractionalPair, n)
    for i, x := range X {
        fractionalPart := x - math.Floor(x)
        fractionalParts[i] = FractionalPair{fractionalPart, i}
    }
    
    // Sort by fractional part in descending order
    sort.Slice(fractionalParts, func(i, j int) bool {
        return fractionalParts[i].fractionalPart > fractionalParts[j].fractionalPart
    })
    
    // Round up the elements with largest fractional parts
    for i := 0; i < roundUpCount; i++ {
        idx := fractionalParts[i].index
        Y[idx]++
    }
    
    return Y
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    public int[] optimalRounding(double[] X) {
        int n = X.length;
        int[] Y = new int[n];
        
        // Calculate target sum (rounded sum of original array)
        double totalSum = 0;
        for (double x : X) {
            totalSum += x;
        }
        int targetSum = (int) Math.round(totalSum);
        
        // Initialize with floor values and calculate current sum
        int currentSum = 0;
        for (int i = 0; i < n; i++) {
            Y[i] = (int) Math.floor(X[i]);
            currentSum += Y[i];
        }
        
        // Calculate how many elements need to be rounded up
        int roundUpCount = targetSum - currentSum;
        
        // Create pairs of (fractional_part, index)
        class FractionalPair {
            double fractionalPart;
            int index;
            
            FractionalPair(double fractionalPart, int index) {
                this.fractionalPart = fractionalPart;
                this.index = index;
            }
        }
        
        List<FractionalPair> fractionalParts = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            double fractionalPart = X[i] - Math.floor(X[i]);
            fractionalParts.add(new FractionalPair(fractionalPart, i));
        }
        
        // Sort by fractional part in descending order
        fractionalParts.sort((a, b) -> Double.compare(b.fractionalPart, a.fractionalPart));
        
        // Round up the elements with largest fractional parts
        for (int i = 0; i < roundUpCount; i++) {
            int idx = fractionalParts.get(i).index;
            Y[idx]++;
        }
        
        return Y;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def optimal_rounding(self, X: List[float]) -> List[int]:
        n = len(X)
        
        # Calculate target sum (rounded sum of original array)
        total_sum = sum(X)
        target_sum = round(total_sum)
        
        # Initialize with floor values and calculate current sum
        Y = [int(x) for x in X]  # floor operation
        current_sum = sum(Y)
        
        # Calculate how many elements need to be rounded up
        round_up_count = target_sum - current_sum
        
        # Create pairs of (fractional_part, index) and sort by fractional part
        fractional_parts = []
        for i, x in enumerate(X):
            fractional_part = x - int(x)
            fractional_parts.append((fractional_part, i))
        
        # Sort by fractional part in descending order
        fractional_parts.sort(reverse=True)
        
        # Round up the elements with largest fractional parts
        for i in range(round_up_count):
            idx = fractional_parts[i][1]
            Y[idx] += 1
        
        return Y

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of the input array. The sorting step dominates the time complexity
  • 🧺 Space complexity: O(n) for storing the fractional parts array and the result array

Method 2 - Mathematical Optimization with Priority Queue

Intuition

We can view this problem as an optimization where we want to minimize the total cost of rounding operations. Each element can be either floored (cost = fractional_part) or ceiled (cost = 1 - fractional_part). We use a priority queue to efficiently track which elements benefit most from being rounded up.

Approach

  1. Calculate target sum and initialize all elements as floored values
  2. For each element, calculate the “benefit” of rounding up (reduction in error)
  3. Use a max-heap to prioritize elements with highest benefit from rounding up
  4. Repeatedly round up elements with highest benefit until target sum is reached
  5. Track the cumulative cost and ensure optimal solution

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    vector<int> optimalRoundingPQ(vector<double>& X) {
        int n = X.size();
        vector<int> Y(n);
        
        // Calculate target sum
        double totalSum = 0;
        for (double x : X) {
            totalSum += x;
        }
        int targetSum = (int)round(totalSum);
        
        // Initialize with floor values
        int currentSum = 0;
        priority_queue<pair<double, int>> pq; // max heap: (benefit, index)
        
        for (int i = 0; i < n; i++) {
            Y[i] = (int)floor(X[i]);
            currentSum += Y[i];
            
            // Benefit of rounding up = reduction in absolute difference
            double fractionalPart = X[i] - Y[i];
            if (fractionalPart > 0) {
                double benefit = fractionalPart; // higher fractional part = higher benefit
                pq.push({benefit, i});
            }
        }
        
        // Round up elements with highest benefit
        int roundUpCount = targetSum - currentSum;
        for (int i = 0; i < roundUpCount && !pq.empty(); i++) {
            auto [benefit, idx] = pq.top();
            pq.pop();
            Y[idx]++;
        }
        
        return Y;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

type BenefitItem struct {
    benefit float64
    index   int
}

type MaxHeap []BenefitItem

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].benefit > h[j].benefit }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
    *h = append(*h, x.(BenefitItem))
}

func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}

func optimalRoundingPQ(X []float64) []int {
    n := len(X)
    Y := make([]int, n)
    
    // Calculate target sum
    totalSum := 0.0
    for _, x := range X {
        totalSum += x
    }
    targetSum := int(math.Round(totalSum))
    
    // Initialize with floor values and build max heap
    currentSum := 0
    h := &MaxHeap{}
    heap.Init(h)
    
    for i, x := range X {
        Y[i] = int(math.Floor(x))
        currentSum += Y[i]
        
        // Calculate benefit of rounding up
        fractionalPart := x - math.Floor(x)
        if fractionalPart > 0 {
            heap.Push(h, BenefitItem{fractionalPart, i})
        }
    }
    
    // Round up elements with highest benefit
    roundUpCount := targetSum - currentSum
    for i := 0; i < roundUpCount && h.Len() > 0; i++ {
        item := heap.Pop(h).(BenefitItem)
        Y[item.index]++
    }
    
    return Y
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public int[] optimalRoundingPQ(double[] X) {
        int n = X.length;
        int[] Y = new int[n];
        
        // Calculate target sum
        double totalSum = 0;
        for (double x : X) {
            totalSum += x;
        }
        int targetSum = (int) Math.round(totalSum);
        
        // Initialize with floor values
        int currentSum = 0;
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0])); // max heap
        
        for (int i = 0; i < n; i++) {
            Y[i] = (int) Math.floor(X[i]);
            currentSum += Y[i];
            
            // Calculate benefit of rounding up
            double fractionalPart = X[i] - Y[i];
            if (fractionalPart > 0) {
                pq.offer(new double[]{fractionalPart, i});
            }
        }
        
        // Round up elements with highest benefit
        int roundUpCount = targetSum - currentSum;
        for (int i = 0; i < roundUpCount && !pq.isEmpty(); i++) {
            double[] item = pq.poll();
            int idx = (int) item[1];
            Y[idx]++;
        }
        
        return Y;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def optimal_rounding_pq(self, X: List[float]) -> List[int]:
        import heapq
        n = len(X)
        
        # Calculate target sum
        total_sum = sum(X)
        target_sum = round(total_sum)
        
        # Initialize with floor values
        Y = [int(x) for x in X]
        current_sum = sum(Y)
        
        # Build max heap of benefits (use negative values for max heap)
        benefits = []
        for i, x in enumerate(X):
            fractional_part = x - int(x)
            if fractional_part > 0:
                # Negative value for max heap behavior
                heapq.heappush(benefits, (-fractional_part, i))
        
        # Round up elements with highest benefit
        round_up_count = target_sum - current_sum
        for _ in range(round_up_count):
            if benefits:
                neg_benefit, idx = heapq.heappop(benefits)
                Y[idx] += 1
        
        return Y

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of the input array. Building the heap takes O(n) and extracting k elements takes O(k log n)
  • 🧺 Space complexity: O(n) for the priority queue and result array

Method 3 - Dynamic Programming with State Optimization

Intuition

We can model this as a dynamic programming problem where for each element, we decide whether to floor or ceil it, subject to the constraint that the total sum must equal the target. This approach explores all possible combinations but can be optimized using memoization.

Approach

  1. Calculate target sum and define DP state as (index, current_sum, operations_used)
  2. For each element, try both floor and ceil operations
  3. Use memoization to avoid recalculating the same states
  4. Track the path that leads to minimum total difference
  5. Reconstruct the optimal rounding decisions from the DP solution

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class Solution {
private:
    unordered_map<string, pair<double, vector<int>>> memo;
    
    string getKey(int idx, int currentSum, int targetSum) {
        return to_string(idx) + "," + to_string(currentSum) + "," + to_string(targetSum);
    }
    
public:
    vector<int> optimalRoundingDP(vector<double>& X) {
        int n = X.size();
        double totalSum = 0;
        for (double x : X) {
            totalSum += x;
        }
        int targetSum = (int)round(totalSum);
        
        memo.clear();
        auto [minDiff, result] = solve(X, 0, 0, targetSum);
        return result;
    }
    
private:
    pair<double, vector<int>> solve(vector<double>& X, int idx, int currentSum, int targetSum) {
        int n = X.size();
        
        // Base case
        if (idx == n) {
            if (currentSum == targetSum) {
                return {0.0, vector<int>()};
            } else {
                return {1e9, vector<int>()}; // Invalid state
            }
        }
        
        string key = getKey(idx, currentSum, targetSum);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }
        
        // Try floor operation
        int floorVal = (int)floor(X[idx]);
        double floorDiff = abs(X[idx] - floorVal);
        auto [floorTotalDiff, floorResult] = solve(X, idx + 1, currentSum + floorVal, targetSum);
        
        if (floorTotalDiff < 1e8) {
            floorTotalDiff += floorDiff;
            floorResult.insert(floorResult.begin(), floorVal);
        }
        
        // Try ceil operation
        int ceilVal = (int)ceil(X[idx]);
        double ceilDiff = abs(X[idx] - ceilVal);
        auto [ceilTotalDiff, ceilResult] = solve(X, idx + 1, currentSum + ceilVal, targetSum);
        
        if (ceilTotalDiff < 1e8) {
            ceilTotalDiff += ceilDiff;
            ceilResult.insert(ceilResult.begin(), ceilVal);
        }
        
        // Choose the better option
        if (floorTotalDiff <= ceilTotalDiff) {
            memo[key] = {floorTotalDiff, floorResult};
        } else {
            memo[key] = {ceilTotalDiff, ceilResult};
        }
        
        return memo[key];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

type DPKey struct {
    idx        int
    currentSum int
    targetSum  int
}

type DPResult struct {
    minDiff float64
    result  []int
}

func optimalRoundingDP(X []float64) []int {
    n := len(X)
    totalSum := 0.0
    for _, x := range X {
        totalSum += x
    }
    targetSum := int(math.Round(totalSum))
    
    memo := make(map[DPKey]DPResult)
    result := solveDP(X, 0, 0, targetSum, memo)
    return result.result
}

func solveDP(X []float64, idx, currentSum, targetSum int, memo map[DPKey]DPResult) DPResult {
    n := len(X)
    key := DPKey{idx, currentSum, targetSum}
    
    // Check memo
    if result, exists := memo[key]; exists {
        return result
    }
    
    // Base case
    if idx == n {
        if currentSum == targetSum {
            return DPResult{0.0, []int{}}
        } else {
            return DPResult{1e9, []int{}} // Invalid state
        }
    }
    
    // Try floor operation
    floorVal := int(math.Floor(X[idx]))
    floorDiff := math.Abs(X[idx] - float64(floorVal))
    floorResult := solveDP(X, idx+1, currentSum+floorVal, targetSum, memo)
    
    if floorResult.minDiff < 1e8 {
        floorResult.minDiff += floorDiff
        floorResult.result = append([]int{floorVal}, floorResult.result...)
    }
    
    // Try ceil operation
    ceilVal := int(math.Ceil(X[idx]))
    ceilDiff := math.Abs(X[idx] - float64(ceilVal))
    ceilResult := solveDP(X, idx+1, currentSum+ceilVal, targetSum, memo)
    
    if ceilResult.minDiff < 1e8 {
        ceilResult.minDiff += ceilDiff
        ceilResult.result = append([]int{ceilVal}, ceilResult.result...)
    }
    
    // Choose the better option
    var finalResult DPResult
    if floorResult.minDiff <= ceilResult.minDiff {
        finalResult = floorResult
    } else {
        finalResult = ceilResult
    }
    
    memo[key] = finalResult
    return finalResult
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

class Solution {
    private Map<String, Result> memo = new HashMap<>();
    
    class Result {
        double minDiff;
        List<Integer> path;
        
        Result(double minDiff, List<Integer> path) {
            this.minDiff = minDiff;
            this.path = new ArrayList<>(path);
        }
    }
    
    public int[] optimalRoundingDP(double[] X) {
        int n = X.length;
        double totalSum = 0;
        for (double x : X) {
            totalSum += x;
        }
        int targetSum = (int) Math.round(totalSum);
        
        memo.clear();
        Result result = solve(X, 0, 0, targetSum);
        return result.path.stream().mapToInt(i -> i).toArray();
    }
    
    private Result solve(double[] X, int idx, int currentSum, int targetSum) {
        int n = X.length;
        String key = idx + "," + currentSum + "," + targetSum;
        
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        // Base case
        if (idx == n) {
            if (currentSum == targetSum) {
                return new Result(0.0, new ArrayList<>());
            } else {
                return new Result(1e9, new ArrayList<>()); // Invalid state
            }
        }
        
        // Try floor operation
        int floorVal = (int) Math.floor(X[idx]);
        double floorDiff = Math.abs(X[idx] - floorVal);
        Result floorResult = solve(X, idx + 1, currentSum + floorVal, targetSum);
        
        if (floorResult.minDiff < 1e8) {
            floorResult = new Result(floorResult.minDiff + floorDiff, floorResult.path);
            floorResult.path.add(0, floorVal);
        }
        
        // Try ceil operation
        int ceilVal = (int) Math.ceil(X[idx]);
        double ceilDiff = Math.abs(X[idx] - ceilVal);
        Result ceilResult = solve(X, idx + 1, currentSum + ceilVal, targetSum);
        
        if (ceilResult.minDiff < 1e8) {
            ceilResult = new Result(ceilResult.minDiff + ceilDiff, ceilResult.path);
            ceilResult.path.add(0, ceilVal);
        }
        
        // Choose the better option
        Result finalResult = (floorResult.minDiff <= ceilResult.minDiff) ? floorResult : ceilResult;
        memo.put(key, finalResult);
        return finalResult;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution:
    def optimal_rounding_dp(self, X: List[float]) -> List[int]:
        from functools import lru_cache
        
        n = len(X)
        total_sum = sum(X)
        target_sum = round(total_sum)
        
        @lru_cache(maxsize=None)
        def solve(idx: int, current_sum: int) -> Tuple[float, Tuple[int, ...]]:
            # Base case
            if idx == n:
                if current_sum == target_sum:
                    return 0.0, ()
                else:
                    return float('inf'), ()  # Invalid state
            
            # Try floor operation
            floor_val = int(X[idx])
            floor_diff = abs(X[idx] - floor_val)
            floor_total_diff, floor_path = solve(idx + 1, current_sum + floor_val)
            
            if floor_total_diff < float('inf'):
                floor_total_diff += floor_diff
                floor_path = (floor_val,) + floor_path
            
            # Try ceil operation
            ceil_val = int(X[idx]) + (1 if X[idx] != int(X[idx]) else 0)
            ceil_diff = abs(X[idx] - ceil_val)
            ceil_total_diff, ceil_path = solve(idx + 1, current_sum + ceil_val)
            
            if ceil_total_diff < float('inf'):
                ceil_total_diff += ceil_diff
                ceil_path = (ceil_val,) + ceil_path
            
            # Choose the better option
            if floor_total_diff <= ceil_total_diff:
                return floor_total_diff, floor_path
            else:
                return ceil_total_diff, ceil_path
        
        min_diff, result_path = solve(0, 0)
        return list(result_path)

Complexity

  • ⏰ Time complexity: O(n × S), where n is the array length and S is the range of possible sums. With memoization, each state is computed once
  • 🧺 Space complexity: O(n × S) for the memoization table and recursion stack

Notes

  • Method 1 (Greedy) is the most efficient and intuitive approach, providing optimal results in O(n log n) time
  • Method 2 (Priority Queue) offers similar performance but with more explicit benefit tracking for educational purposes
  • Method 3 (Dynamic Programming) provides a complete exploration of all possibilities but with higher time complexity
  • The greedy approach works optimally because the problem has the greedy choice property: locally optimal choices (rounding up elements with largest fractional parts) lead to globally optimal solution
  • All methods handle edge cases like arrays with integer values, negative numbers, and various sum constraints
  • The algorithm maintains the mathematical property that minimizing total absolute difference while preserving sum is equivalent to minimizing the cost of rounding operations
  • Real-world applications include financial systems, statistical analysis, and data processing where precision and sum preservation are critical
  • The problem demonstrates the effectiveness of greedy algorithms in optimization scenarios with specific mathematical properties