Official algorithmic problem description and constraints.
You have N table legs, of different strengths. Pillar i can bear a weight of W i , and will break if it has to bear a larger weight. You'd like to construct a table using some non-empty subset of these table legs. When you place a weight on a table, its load is equally distributed to each of its legs. For example, if you build a table with 4 4 legs, and place a weight of 18 18 on it, each leg will need to bear a weight of 18 4 = 4.5 4 18 =4.5. So for instance, a table whose legs have strengths [ 4 , 4 , 5 , 6 ] [4,4,5,6] will not be able to bear this weight (the two legs with strength 4 4 will break), whereas a table with leg strengths [ 5 , 6 , 6 , 8 ] [5,6,6,8] will be able to bear it. Find the maximum possible weight that a table built out of some of these N legs can bear, without any of the legs breaking. It can be proved that this maximum weight is always an integer. Note: Subsets need not be contiguous: for example, [ 1 , 3 ] [1,3] is a subset of [ 1 , 4 , 3 , 2 ] [1,4,3,2].
Detailed video explanations, mathematical intuition, and clean C++ implementation code.
