Re: Algorithms Homework Help?!?!

[Adam Beneschan <adam@irvine.com>]

On Wednesday, January 16, 2013 2:27:48 PM UTC-8, Robert A Duff wrote:

> > On top of that, I don't think this homework assignment can be done
> > with an O(log N) algorithm. ...
> 
> Oh, OK.  I didn't look at it carefully.

I looked at it a bit more.  There are two variables involved: the size of the array, and the largest number in the array.  My gut feeling was that the algorithm's time shouldn't depend on the largest value in the array.  But I'm no  longer sure.  The issue boils down to this: Suppose you have an array A(1..m) of positive integers; you can define a function f(n) = floor(A(1)/n) + floor(A(2)/n) + ... + floor(A(m)/n).  This is monotonically nonincreasing.  The problem is, given some value K, to find the largest n such that f(n) >= K.  Finding the best way to solve this problem seems like an interesting problem in number theory, and I don't know how to solve it.  Given that, and since the function is nonincreasing, using a binary search to find the answer seems reasonable.  Maybe there's a better way, though.

                            -- Adam