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)