# Interview q: Small possible length of stick from an array of stick lengths

I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here might be able to help?

Statement: Given m sticks with different lengths. Combine these sticks to form longer sticks with the same length. What’s the smallest possible length of these newly unified sticks?

Conditions:

• Must use all sticks
• m < 50
• max length of single stick less than 20

Example:

Input: 5 2 1 5 2 1 5 2 1
Output: 6
(Process: 1+5, 1+5, 1+5, 2+2+2)


Input: 3 3 3 2 2 5
Output: 9
(Process: 3+3+3, 2+2+5)


Input: 1 2 3 4 5
Output: 5
(Process: 2+3, 1+4, 5)


Input: 1 3 4 5
Output: 13
(Process: 1+3+4+5)

• Just wondering: what company asked you this question? I had interviews in companies like Amazon and Facebook, and their questions never were nearly that hard. When you fix the desired length, Bin packing problem, which is Strongly NP-complete, can be reduced to this problem. So, unless I'm missing something, you didn't have a hope to solve this problem efficiently.
– user114966
Aug 6, 2020 at 0:38
• And while constraints are small, I don't see how to use them. When the number of bins (the number of groups) is small (e.g. 2,3), you can use dynamic programming. If it's large ($\ge 25$), there are also simple approaches. But for values in between (e.g. 10) I don't see what to do
– user114966
Aug 6, 2020 at 2:06