# Round numbers

• Was asked in airbnb phone screen

When you book on airbnb the total price is:

Total price = base price + service fee + cleaning fee + ...

input : array of decimals ~ X
output : array of int ~ Y

But they need to satisfy the condition:

1. sum(Y) = round(sum(x))
2. minmize (|y1-x1| + |y2-x2| + ... + |yn-xn|)

Example1:
input = 30.3, 2.4, 3.5
output = 30 2 4

Example2:
input = 30.9, 2.4, 3.9
output = 31 2 4

• Thanks for posting!
Interesting question~ It is better that you separate your post into two, since you give an answer.

• I wanted to write my thought down, after reading your code. I abandon it.
Clever thought and clean code~ good!
Here is python code based on your thought:

``````from math import floor

def roundNumbers(input):
output = map(lambda x: floor(x), input)
remain = round(sum(input) - sum(output))

it = sorted(enumerate(input), key=lambda i: i[1] - floor(i[1]))
for _ in range(remain):
output[it.pop()[0]] += 1

return output

``````

• This post is deleted!

• This post is deleted!

• @xidui said in Round numbers:

Clever thought and clean code~ good!
Here is python code based on your thought:

Hi,
can you please explain what you are doing ?

• @xidui Will really appreciate if you can explain your code.

• Java Solution:-

``````package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MinimizeRoundedSum {

class RoundedNumber {
float input, res;
int index, output;

public RoundedNumber(int index, float input, int output, float res) {
this.index = index;
this.input = input;
this.output = output;
this.res = res;
}
}

private int[] minimize(float[] input) {
if (null == input) {
return new int[-1];
}

int len = input.length;
int output[] = new int[len];

if (len == 1) {
output[0] = Math.round(input[0]);
return output;
}

List<RoundedNumber> list = new ArrayList<>();

float sumInputFloat = 0.0f;
for (float val : input) {
sumInputFloat += val;
}

int sumInput = Math.round(sumInputFloat);

int sumOutput = 0;
for (int index = 0; index < len; index++) {
output[index] = Math.round(input[index]);
sumOutput += output[index];

list.add(new RoundedNumber(index, input[index], output[index], Math.abs(input[index] - output[index])));
}

int res = sumInput - sumOutput;

Collections.sort(list, new Comparator<RoundedNumber>() {
@Override
public int compare(RoundedNumber r1, RoundedNumber r2) {
if (r1.res > r2.res) {
return 1;
} else if (r1.res < r2.res) {
return -1;
} else {
return 0;
}
}
});

for (RoundedNumber val : list) {
// System.out.print(val.input + " ");
}

int start = 0, end = len - 1;
while (res > 0 && end >= 0) {
int val = list.get(end).output + 1;
float valRes = Math.abs(val - list.get(end).input);

if (valRes >= 0 && valRes <= 1) {
list.set(end, new RoundedNumber(list.get(end).index, list.get(end).input, val, list.get(end).res));
--res;
}

--end;
}

while (res < 0 && start < len) {
int val = list.get(start).output - 1;
float valRes = Math.abs(val - list.get(start).input);

if (valRes >= 0 && valRes <= 1) {
list.set(start,
new RoundedNumber(list.get(start).index, list.get(start).input, val, list.get(start).res));
++res;
}

++start;
}

for (RoundedNumber rNum : list) {
output[rNum.index] = rNum.output;
}

return output;
}

public static void main(String[] args) {
MinimizeRoundedSum obj = new MinimizeRoundedSum();

float input1[] = { 2.4f, 3.3f, 3.9f, 20.1f, 30.3f };
float input2[] = { 2.4f, 3.4f, 3.4f, 20.4f, 30.4f };
float input3[] = { 2.5f, 3.5f, 3.5f, 20.5f, 30.5f };

int output[] = obj.minimize(input3);

for (int val : output) {
System.out.println(val);
}
}

}
``````

• @xidui There can't be a float in range method!

• from math import floor
def roundNumbers(input):

``````print 'input:',input
output = map(lambda x: int(floor(x)), input)
remain = int(round(sum(input) - sum(output)))
print 'after floor:',output
print 'remaining:',remain
it = sorted(enumerate(input), key=lambda i: floor(i[1])+1-i[1])
print 'sort_result:',it

for i in range(0,remain):
index=it[i][0]
output[index]+=1
print 'final_output:',output
return output``````

• `````` public static int[] findRound(double[] arr) {
int[] result = new int[arr.length];

double sum = 0;
int floorSum = 0;
Map<Integer, Double> decimalMap = new TreeMap<Integer, Double>();

for(int i=0;i<arr.length;i++) {
result[i] = (int)Math.floor(arr[i]);
String decimal = String.format("%.1f", arr[i] - Math.floor(arr[i]));
decimalMap.put(i, Double.parseDouble(decimal));
floorSum+=Math.floor(arr[i]);
sum+=arr[i];
}

double remaining =  Math.round(sum) - floorSum;
if(remaining == 0) {
return result;
}

Map<Integer, Double> sortedMap = sortByValue(decimalMap);
Integer[] keySet = sortedMap.keySet().toArray(new Integer[sortedMap.size()]);
for(int i=0;i<remaining;i++) {
result[keySet[i]]++;
}
return result;
}

public static  Map<Integer, Double> sortByValue(Map<Integer, Double> map) {
List<Map.Entry<Integer, Double>> mapList = new LinkedList<>(map.entrySet());

Collections.sort(mapList, new Comparator<Map.Entry<Integer, Double>>() {
@Override
public int compare(Map.Entry<Integer, Double> o1, Map.Entry<Integer, Double> o2) {
return (o2.getValue()).compareTo(o1.getValue());
}
});

Map<Integer, Double> m = new LinkedHashMap<>();
for(Map.Entry<Integer, Double> cur: mapList) {
m.put(cur.getKey(), cur.getValue());
}
return m;
}``````

• ``````struct myClass {
bool operator() (pair<int,double>p1, pair<int,double>p2) {
return (p1.second < p2.second)?true:false;
}
} mySort;
vector<int> roundFunc(vector<double> input) {
vector<int> res;
if(input.size()==0)
return res;
if(input.size()==1) {
res.push_back(int(round(input[0])));
return res;
}
res.resize(input.size());
double inputSum = accumulate(input.begin(),input.end(),0.0);
int sum = round(inputSum);
int lessSum = 0;
vector<pair<int,double>> temp;
for(int i=0;i<input.size();i++) {
double diff = input[i] - floor(input[i]);
temp.push_back(make_pair(i,diff));
lessSum += floor(input[i]);
res[i] = floor(input[i]);
}
//sort by diff
sort(temp.begin(),temp.end(),mySort);
int gap = sum - lessSum;
for(int i=input.size()-gap;i<input.size();i++) {
//i is original index
int index = temp[i].first;
res[index]++;
}
return res;
}
``````

• @nullpointerP Is that any theory behind this? Thanks!.

• @dukeforever I just posted a C++ version based on the stackoverflow reference link. Acturally I think both floor and ceil is OK because finally we need to make up for the gap between the current sum and the real sum.

• ``````public class Pair {
double diff;
int idx;

public Pair(double dif, int index){
this.diff = dif;
this.idx = index;
}

}

public int[] solution(double[] input){
double doubleSum = 0;
int floorSum = 0;
List<Pair> list = new ArrayList<>();

for(int i=0; i<input.length; i++){
double d = input[i];

doubleSum += d;
floorSum += Math.floor(d);
Pair p = new Pair(d-Math.floor(d), i);
}
//here we calculate how many numbers needed to be round up
int numTobeUP = (int)Math.round(doubleSum) - floorSum;

//reverse order of list from big to small
//then pick pick the ceilling of bigger elements
Collections.sort(list,  new Comparator<Pair>(){
@Override
public int compare(Pair p1, Pair p2){
return Double.compare(p1.diff, p2.diff) * (-1);
}
});

int[] res = new int[input.length];
System.out.println("to be up: " + numTobeUP);;

for(int i=0; i<numTobeUP; i++){
Pair p = list.get(i);
res[p.idx] = (int) Math.ceil(input[p.idx]);
}
for(int i=numTobeUP; i<input.length; i++){
Pair p = list.get(i);
res[p.idx] = (int) Math.floor(input[p.idx]);
}

return res;
}
`````````

• This post is deleted!

• Compute the loss when the number is rounded up and rounded down.
Add this loss to the deviation computed so far. if the cumulative loss of deviation+roundeddown less than deviation+roundedup, round the number down. Else round the number up.
The goal is to keep the deviation minimal at any given index.

``````private List<Integer> roundSum(List<Double> list) {
List<Integer> output = new ArrayList<>();
double deviation = 0;
double lossroundedup = 0;
double lossroundeddown = 0;
for(int i=0;i<list.size();i++) {
lossroundedup = Math.ceil(list.get(i)) - list.get(i);
lossroundeddown = Math.floor(list.get(i)) - list.get(i);
if(Math.abs(deviation+lossroundeddown) < Math.abs(deviation+lossroundedup)) {
deviation += lossroundeddown;
} else {