 Hi

I have the following python code snippet to solve the Paying Up problem .

The tests pass as expected on my computer based on the sample input provided but when I upload the
same I get a WA .

``````from sys import stdin

for t in xrange(T):

sum=0
wallet=list()
filter_wallet=list()

for n in xrange(notes):
wallet.append(i)

wallet.sort(reverse=True)
filter_wallet=filter(lambda x: x <=demand ,wallet)

for c in filter_wallet:

if (sum + c )<= demand:
sum=sum + c

print "Yes" if sum == demand else  "No"
``````

Am I making any mistake …?

if i understand correctly, your algorithm seems wrong.

you’re starting from the highest note value under the demand, and adding them as long as the sum does not exceed the demand. but it could fail.

let’s take this example :

``````1
3 10
9
5
5
``````

your program says ‘No’, although it’s possible with 5+5.

adding 9 from the very beginning prevents any future combination.

you should look for another reliable algorithm to do that (with dynamic programming for example here).

am i wrong somewhere ?