title: Number Sequences
body: <p>I've got a homework about number sequences. Given array of <strong>n</strong> elements from <strong>1</strong> to <strong>MAX</strong>. We can choose any number become <strong>start</strong>. We can multiply <strong>start</strong> by 2, or divided it by 2, but if the start is already odd number we can't divided it. The task is we must minimize the total of differences for each number in the array.
  <br/> <br/>For example
  <br/> arr[]={2,4,7,32,16} The output is 1, because we can choose 1 as the <strong>start</strong>. For each element we must make this number greater and closer to the elements.
  <br/>
  <br/> We traverse through the array.
  <br/> For n=0; The element is 2. So we multiply <strong>start</strong> by 2, 1 time <strong>start=2</strong> so the difference is 2-2=0;
  <br/> For n=1; The element is 4. So we multiply <strong>start</strong> by 2, 1 time <strong>start=4</strong> so the difference is 4-4=0;
  <br/> For n=2; The element is 7. So we multiply <strong>start</strong> by 2, 1 time <strong>start=8</strong> so the difference is 8-7=1;
  <br/> For n=3; The element is 32. So we multiply <strong>start</strong> by 2, 2 time <strong>start=32</strong> so the difference is 32-32=0;
  <br/> For n=4; The element is 16. So we divided <strong>start</strong> by 2, 1 time <strong>start=16</strong> so the difference is 16-16=0;
  SO TOTAL DIFFERENCES=0+0+1+0=1;
  <br/>
  <br/> If we choose start=3 then it becomes
  <br/> For n=1; The element is 4. So we multiply <strong>start</strong> by 2, 1 time <strong>start=6</strong> so the difference is 6-4=2;
  <br/> For n=2; The element is 7. So we multiply <strong>start</strong> by 2, 1 time <strong>start=12</strong> so the difference is 12-7=5;
  <br/> For n=3; The element is 32. So we multiply <strong>start</strong> by 2, 2 time <strong>start=48</strong> so the difference is 48-32=16;
  <br/> For n=4; The element is 16. So we divided <strong>start</strong> by 2, 1 time <strong>start=24</strong> so the difference is 24-16=8;
  SO TOTAL DIFFERENCES=2+5+16+8=31;
  <br/>
  <br/>
  We can see that for <strong>start=1</strong> the output is minimum than all numbers by brute-forcing each number from <strong>1</strong> to <strong>MAX</strong>.
  <br/>
  <br/>To solve this problem i've got idea.</p>
  <blockquote>
  <ol>
  <li>For <strong>start</strong> we choose all odd number from <strong>1</strong> to <strong>MAX</strong>.<br/>
  2. Then i brute-force all the possible <strong>start</strong> for every elements to get the minimum.</li>
  </ol>
  </blockquote>
  <p>This is the PASCAL code</p>
  <pre><code>uses math;
  var
    data: array[1..1000100] of longint;
    s: string[7];
    n, i, j, min, ansn, ansb, sub: longint;
  
    function minimum(a, b: longint): longint;
    begin
      if a &gt; b then
        minimum := b
      else
        minimum := a;
    end;
  
    function hitung(a: longint): longint;
    var
      x, hit, ca, tot, b: longint;
    begin
      hit := 0;
      tot := 0;
      for x := 1 to n do 
      begin
        hit := hit + data[x];
  
        b := a;
  
        while b &lt; data[x] do 
        begin
          b := b * 2;
        end;
  
        tot := tot + b;
      end;
      hitung := tot - hit;
    end;
  
  begin
    readln(s);
    readln(n);
    sub := 1000000;
    for i := 1 to n do
      read(data[i]);
  
    ansb:=hitung(1);
  
    j:=1;
  
    while ((ansb &gt; 0) and (j &lt;= sub)) do
    begin
      ansn := hitung((2 * (j)) + 1);
      min := minimum(ansb, ansn);
      ansb := min;
      j := j + 1
    end;
  
    writeln(min);
  end.
  </code></pre>
  <p>&lt;br&gt;
  It works for small <strong>MAX</strong> but the hint of solution said that the solution is using prefix-sum, with O(<strong>MAX</strong>/2). While my solution is O(<strong>MAX</strong>/2*N). I don't know where to insert the prefix sum. How we can do that? Thanks in advance!</p>