Statement

Given a ribbon of length n and a set of possible sizes, cut the ribbon in sizes such that n is achieved with the maximum number of pieces.

You have to return the maximum number of pieces that can make up n by using any combination of the available sizes. If the n can’t be made up, return -1, and if n is 0, return 0.

Let’s say, we have a ribbon of length 1313 and possible sizes as [5,3,8][5, 3, 8]. The ribbon length can be obtained by cutting it into one piece of length 55 and another of length 88 (as 5+8=135 + 8 = 13), or, into one piece of length 33 and two pieces of length 55 (as 3+5+5=133 + 5 + 5 = 13). As we wish to maximize the number of pieces, we choose the second option, cutting the ribbon into 33 pieces.

Constraints:

  • 11 \leq sizes.length 12\leq 12

  • 11 \leq sizes[i] 2311\leq 2^{31} -1

  • 00 \leq n 1500\leq 1500

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.