From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.8 required=5.0 tests=BAYES_00,PLING_QUERY autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,7d1a02b763945274 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit X-Received: by 10.66.72.131 with SMTP id d3mr379134pav.38.1358379803211; Wed, 16 Jan 2013 15:43:23 -0800 (PST) X-Received: by 10.50.163.67 with SMTP id yg3mr2606476igb.12.1358379803170; Wed, 16 Jan 2013 15:43:23 -0800 (PST) Path: s9ni26pbb.0!nntp.google.com!f6no3500198pbd.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Wed, 16 Jan 2013 15:43:22 -0800 (PST) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=66.126.103.122; posting-account=duW0ogkAAABjRdnxgLGXDfna0Gc6XqmQ NNTP-Posting-Host: 66.126.103.122 References: <183f4095-ac19-4396-a910-ba9cadfb958b@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <660d1b25-e1ea-48c5-a37c-1682c70b7a2e@googlegroups.com> Subject: Re: Algorithms Homework Help?!?! From: Adam Beneschan Injection-Date: Wed, 16 Jan 2013 23:43:23 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2013-01-16T15:43:22-08:00 List-Id: 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. ... >=20 > Oh, OK. I didn't look at it carefully. I looked at it a bit more. There are two variables involved: the size of t= he 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 arr= ay A(1..m) of positive integers; you can define a function f(n) =3D floor(A= (1)/n) + floor(A(2)/n) + ... + floor(A(m)/n). This is monotonically noninc= reasing. The problem is, given some value K, to find the largest n such th= at f(n) >=3D K. Finding the best way to solve this problem seems like an i= nteresting problem in number theory, and I don't know how to solve it. Giv= en 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