Round numbers


  • 7
    S

    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


  • 0

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


  • 5

    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
            
    

  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    G

    @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 ?


  • 0

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


  • 2

    Reference:-
    http://stackoverflow.com/questions/792460/how-to-round-floats-to-integers-while-preserving-their-sum

    Algorithm:-
    http://static.ellipsix.net/ext-tmp/roundingtest.py

    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);
    		}
    	}
    
    }
    

  • 0
    M

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


  • 0
    X

    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

  • 3
    S
     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;
        }

  • 1
    N
    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;
    }
    

  • 0
    D

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


  • 0
    N

    @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.


  • 2
    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);
    			list.add(p);
    		}
    		//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;
    	}
    	```

  • 0
    H
    This post is deleted!

  • 0
    K

    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)) {
    				output.add((int)Math.floor(list.get(i)));
    				deviation += lossroundeddown; 
    			} else {
    				output.add((int)Math.ceil(list.get(i)));
    				deviation += lossroundedup;
    			}
    		}
    		return output;
    	}
    

  • 0
    H

    @kmv Your coder returns [30, 3, 3] for the test case [30.3, 2.4, 3.5]. The right result should be [30, 2, 4].


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.