title: Rescale a vector of integers
body: <p>Assume that I have a vector, V, of positive integers. If the sum of the integers are larger than a positive integer N, I want to rescale the integers in V so that the sum is &lt;= N. The elements in V must remain above zero. The length of V is guaranteed to be &lt;= N.</p>
  
  <p>Is there an algorithm to perform this rescaling in linear time?</p>
  
  <p>This is not homework, BTW :). I need to rescale a map from symbols to symbol frequencies to use range encoding.</p>
  
  <p>Some quick thinking and googling has not given a solution to the problem.</p>
  
  <p>EDIT:</p>
  
  <p>Ok, the question was somewhat unclear. "Rescale" means "normalize". That is, transform the integers in V, for example by multiplying them by a constant, to smaller positive integers so the criterion of sum(V) &lt;= N is fulfilled. The better the ratios between the integers are preserved, the better the compression will be.</p>
  
  <p>The problem is open-ended in that way, the method does not need to find the optimal (in, say, a least squares fit sense) way to preserve the ratios, but a "good" one. Setting the entire vector to 1, as suggested, is not acceptable (unless forced). "Good" enough would for example be finding the smallest divisor (defined below) that fulfills the sum criterion.</p>
  
  <p>The following naive algorithm does not work.</p>
  
  <ol>
  <li>Find the current sum(V), Sv</li>
  <li>divisor := int(ceil(Sv/N))</li>
  <li>Divide each integer in V by divisor, rounding down, but not to less than 1.</li>
  </ol>
  
  <p>This fails on v = [1,1,1,10] with N = 5.</p>
  
  <pre><code>divisor = ceil(13 / 5) = 3.
  V := [1,1,1, max(1, floor(10/3)) = 3]
  Sv is now 6 &gt; 5.
  </code></pre>
  
  <p>In this case, the correct normalization is [1,1,1,2]</p>
  
  <p>One algorithm that would work is to do a binary search for divisor (defined above) until the smallest divisor in [1,N] fulfilling the sum criterion is found. Starting with the ceil(Sv/N) guess. This is however, not linear in number of operations, but proportional to len(V)*log(len(V)).</p>
  
  <p>I am starting to think that it is impossible to do well, in linear time, in the general case. I might resort to some sort of heuristic.</p>