Optimal Array Rounding with Sum Preservation
MediumUpdated: Aug 10, 2025
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
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
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
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
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
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
- Calculate the target sum by rounding the sum of all elements in the input array
- Initialize result array by flooring all input elements
- Calculate current sum of floored elements
- Determine how many elements need to be rounded up to reach target sum
- Create array of (fractional_part, index) pairs and sort by fractional part in descending order
- Round up the elements with largest fractional parts until target sum is reached
- Return the resulting integer array
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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
- Calculate target sum and initialize all elements as floored values
- For each element, calculate the "benefit" of rounding up (reduction in error)
- Use a max-heap to prioritize elements with highest benefit from rounding up
- Repeatedly round up elements with highest benefit until target sum is reached
- Track the cumulative cost and ensure optimal solution
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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
- Calculate target sum and define DP state as (index, current_sum, operations_used)
- For each element, try both floor and ceil operations
- Use memoization to avoid recalculating the same states
- Track the path that leads to minimum total difference
- Reconstruct the optimal rounding decisions from the DP solution
Code
C++
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];
}
};
Go
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
}
Java
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;
}
}
Python
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