for which case is this logic wrong ?

general
,
1

A1 Problem - CodeChef :- this is the link to my question

my solution is this :-

t=int(input())

while(t):

n,m=map(int,input().split())

a=[]
for i in range(0,n):
    a.append(int(input()))
a=sorted(a,reverse=True)

while(m>0):
    flag=0
    for i in a:
        if(i<=m):
            flag=1
            m=m-i
            a.remove(i)
            break
    if(flag==0):
            break
        
    
if(m==0):
    print('Yes')
else:
    print('No')
t-=1

this logic is giving wrong answer but i do not understand for which case .

2

https://discuss.codechef.com/questions/128625/payinguppractice-problem-help-me?page=1#128629

Have a look at this. I think you have also done the same mistake.

1 Like
3

Here is the test case consider n=4 and m=11 and notes - 6,4,3,2
,i.e.,1
4 11
6
4
3
2 your code is giving output No but ans is Yes (6+3+2=11) your greedy approach of always taking the biggest number fails. it takes first 6 then 4 left money is 1 but if it takes instead of taking 4, takes 3 and 2 so leftmoney=0. Hope you find it helpful

1 Like
4

thank you very much brother.

5

thank you bro