Crates of Equal Weight
weights are the weights of some parcels. Pack all of them into crates so that every crate ends up weighing the same, and use as many crates as you can. Each parcel goes into exactly one crate, and no crate stays empty.
Return the largest possible number of crates.
Example 1
weights [6,2,4,3,3,6]
returns 4
Four crates of weight 6: 6, 6, 2 + 4 and 3 + 3. More crates would have to weigh less than the parcel of weight 6.
Example 2
weights [5,1,1,1]
returns 1
The parcel of weight 5 is more than half of the total 8, so everything goes into one crate.
Example 3
weights [2,2,2]
returns 3
Every parcel gets a crate of its own.
Constraints
1 <= len(weights) <= 121 <= weights[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.