CODEWITHSUNDEEP
python
Raphael Kwami
Raphael Kwami

Reputation: 13

Find if a number is a possible sum of two or more numbers in a given set - python

The office supply store sells your favorite types of pens in packages of 5, 8 or 24 pens. Thus, it is possible, for example, to buy exactly 13 pens (with one package of 5 and a second package of 8), but it is not possible to buy exactly 11 pens, since no non-negative integer combination of 5's, 8's and 24's add up to 11. To determine if it is possible to buy exactly n pens, one has to find non-negative integer values of a, b, and c such that

5a + 8b + 24c = n

Write a function, called numPens that takes one argument, n, and returns True if it is possible to buy a combination of 5, 8 and 24 pack units such that the total number of pens equals exactly n, and otherwise returns False.

Note: it was a question that came up in a mid sem exams, that was last month. i was unable to solve it but am still looking for the solution. any help will be accepted. the code in python or an algorithm to solve it. thanks

Upvotes: 1

Views: 296

Answers (1)

Jeremy Roman
Jeremy Roman

Reputation: 16355

This sounds like a good candidate for dynamic programming.

def numPens(n):
  pen_sizes = [5, 8, 24]
  results = [True]
  for i in range(1, n+1):
    results.append(any(i >= size and results[i - size] for size in pen_sizes))
  return results[n]

The key insights here are:

  1. 0 pens can be achieved (trivially: 0 packs of each size).
  2. We can figure out whether we can get n pens if we already know the answers for fewer than n pens.

For example, let's say we want to know whether we can get 10 pens, supposing we already know the answers for 0 through 9. Well, we'll need at least one pack to do so. Then there are 3 cases to consider:

  1. Pack of 5 + however we get 5 pens, if it's possible to get 5 pens.
  2. Pack of 8 + however we get 2 pens, if it's possible to get 2 pens.
  3. Pack of 24 + however we get -14 pens, if it's possible to get -14 pens.

The last of these is nonsensical, so getting 10 pens is possible if (and only if) it is possible either to get 5 pens or to get 2 pens. Since we have assumed we already know the answers for 0 to 9, we can solve the problem (it turns out that 5 pens is possible, as a pack of 5, so we conclude that 10 is as well).

So in order to put ourselves in the situation where we always have the answers for the smaller values of n, we start with the obvious answer for 0. Then we compute the answer for 1 (since we have the answer for 0 already, we can do this). Then we compute the answer for 2 (since we have 0 and 1 already, we can do this), and so on, until we have the answer for the n we want.

This bit of code encapsulates the actual calculation of the result from the previous results: it produces True if there is any pack size size for which it makes sense to buy a pack of that size (without getting a negative number for i - size), and we have previously found a way to buy i - size pens.

any(i >= size and results[i - size] for size in pen_sizes)

The rest of the code simply lets us store that result in the results list for future use, and ultimately return the final result.

Upvotes: 3

Related Questions