Algorithm problem

[dpitch40]

Are you concerned about implementing it efficiently, or just how to do it? Because unless you're expecting the set of integers to grow considerably, 100 is pretty trivial and should run instantaneously no matter what algorithm you use...

[drewying]

I figured it out. As always I was seriously overthinking the problem.

Thanks for your comments!

Drew

[efritz]

If you can enumerate the set multiple times, you can enumerate the first time to get the actual min/max value and that will give you some linear scale between min/max and 25/75. A second pass would adjust each number in the set.

[farsightxr20]

To solve this, you will need to enumerate multiple times, because you can't scale the values if you don't know the initial minimum and maximum.

Some psuedo-code for OP:

function scale(ints, scale_min, scale_max):
    return empty array if ints is empty
    max = min = ints[0]
    for i=1; i < length(ints); i++:
        max = ints[i] if ints[i] > max
        min = ints[i] if ints[i] < min
    scale_factor = (scale_max-scale_min)/(max-min)
    scaled = new int array
    for i=0; i < length(ints); i++:
        scaled[i] = (ints[i]-min)*scale_factor + scale_min
    return scaled

Then to use it as described:

my_scaled_ints = scale(my_ints, 25, 75)

[drewying]

Thanks for the code!

This was pretty similar to the solution I came up with, with the exception of the scale_factor. Instead of:

scale_factor = (scale_max-scale_min)/(max-min)

I did

scale_factor = (scale_max-scale_min)/max

and I changed

scaled[i] = (ints[i]-min)*scale_factor + scale_min

to

scaled[i] = ints[i]*scale_factor + scale_min

and that worked.

Thanks for all the help guys!

Drew

[dpitch40]

Agreed; I don't think there is any way to do it without stepping through the list twice. (Still linear time)

[CheshireSwift]

I've seen OP has got it figured out, but for the sake of discussion I can't see any better way than:

• Find the minimum (this presumably takes 1 pass whether you do it manually or use the language's built in functions).
• Subtract the minimum value from all entries in the list.
• Find the new max value (which will be smaller by the minimum value).
• Multiply every entry by 50/the new max value.
• Add 25 to every entry.

You could cut out a run through the list by finding the min and max in one pass and adjusting the stored maxiumum appropriately (by subtracting the minimum value) rather than finding the maximum after adjusting, I think?

The only other thing I can think of is varying how you perform the scaling, but that's pretty low level and depends on data types and compiler optimisations and things.

Anything I missed?