algorithm to spread linear range of integral numbers to bigger array

Question

Problem

1. there are integral numbers for eg. i = <102,150>, what represents 49 numbers (102,103,...150)
2. there is an empty array a[60], so size is 60 free 'slots'
3. need an algorithm, how to spread 49 numbers to an array of 60 slots as evenly as possible, it is obvious that some numbers have to be repeated to fill all 60 slots, exactly 12
4. there is no free memory to count all upfront(a[] can be the size of 10000 as well), the algorithm must work like a stream, so it will return number for particular index a[0], a[1], a[2],... when it asks for it.
5. it must be fast because the consumer has a time slot to pick up the values

Example

In the following example, all is beautifully aligned

    i = <10, 14> => 5 numbers  
    a[10]  => 10 slots

expected result

    a[0] = 10  
    a[1] = 10  
    a[2] = 11  
    a[3] = 11  
    a[4] = 12  
    a[5] = 12  
    a[6] = 13  
    a[7] = 13  
    a[8] = 14  
    a[9] = 14

hope I have described it clearly to understand :-),

I have done some implementation already but it does not distribute as evenly as I wish

thanks for all answers or at least pointing in the right direction

Answer 1

Look into how to store a binary tree as an array.

Basically, as you stream the numbers, you build the binary array, at any point you can expand the binary tree Taking a binary tree that requires only uses up 49 spots to 60 spots, just by copying the parent value down to it's children (if the child doesn't have a value).

The tricky bit might be ensuring you know what is a "copied value" and what is an actual value.

Idea here is to avoid expanding as much as possible, as it makes everything else take longer.

You can get a[0], a[1], a[2] working as you want by wrapping the array in a utility that works out where the element is based on the requested index. IE: a[45] = a.at_index(45). Alternatively, you might meant hat you actually want something like a.next() (first call gives a[0] second call gives a[1] and so on.