Re: [algogeeks] Partition the array with equal average

You can reduce this problem to the sum-subset problem . Let A be the array. Compute S = A[0] + ... + A[N-1], where N is the length of A. For k from1 to N-1, let T_k = S * k / N. If T_k is an integer, then find a subset of A of size k that sums to T_

Re: [algogeeks] Partition the array with equal average

Are U asking the Code Again ?? :) On Fri, May 18, 2012 at 2:19 PM, saurabh singh wrote: > > Saurabh Singh > B.Tech (Computer Science) > MNNIT > blog:geekinessthecoolway.blogspot.com > > > > On Thu, May 17, 2012 at 11:40 PM, Prem Krishna Chettri > wrote: > >> I guess this is Subset minimization

Re: [algogeeks] Partition the array with equal average

Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Thu, May 17, 2012 at 11:40 PM, Prem Krishna Chettri wrote: > I guess this is Subset minimization problem's Modification.. > > > Algo.. > > 1> Get all the Subset of the particular array. Best Algo O(n2). > ''

Re: [algogeeks] Partition the array with equal average

I guess this is Subset minimization problem's Modification.. Algo.. 1> Get all the Subset of the particular array. Best Algo O(n2). 2> Now try to find the subsets having similar average. Again best algo known is O(n2). Anyone have better options?? BR, Prem On Fri, May 18, 2012 at 12:05 PM, p

[algogeeks] Partition the array with equal average

How do you partition an array into 2 parts such that the two parts have equal average?...each partition may contain elements that are non-contiguous in the array... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on