algorithm - Normalizing integers -

i have list of integers , want normalize them sum let's 100. instance (1, 1, 1, 1) --> (25, 25, 25, 25). relatively easy achieve:

int sum = calcsum(list); double factor = 100.0 / sum; list<integer> newlist = lists.newarraylist(); (integer : list) {   newlist.add(i*factor); } 

this works long sum divisor of 100. unfortunately maps (1, 2) --> (33, 66) instead of (1, 2) --> (33, 67). can add rounding solution

newlist.add(i*factor); --> newlist.add(math.round(i*factor)); 

unfortunately still has problem (1, 1, 1) --> (33, 33, 33). realize in case need add sort of tiebreaker , arbitrarily choose 1 of entries 34. let's ratios (0.334, 0.333, 0.333) want choose first element , not make arbitrary choice. in case of perfect tie, choosing 1 element @ random increment 1 isn't enough because might have increment more 1.

i come inelegant algorithm repeatedly chooses max (without choosing same element twice , arbitrary tiebreaker) , increments until sum 100. there nicer algorithm this?

instead of floating point division, can use integer division remainder.

private static int [] divide(int ... num) {     int [] ret = new int[num.length];     int sum = sum(num);     int rem = 0;     (int = 0; < ret.length; i++) {         int count = num[i]*100 + rem;         ret[i] = count / sum;         rem = count % sum;     }     return ret; } 

as can see, carry remainder next iteration , add back. feeding remainder in next iteration know when need add "leap number" in reach exact total score of 100.

the problem here number added last element, i'll let figure out how change that. :)

this idea of keeping track of error , feeding powerful general strategy, used in many algorithms, notably in bresenham line drawing algorithm.