# Tutorial for problem “Paying Up”

Hello,

The problem “Paying Up” was one of the easy ones in the March 2009 contest on Codechef. It is considered an easy problem, because it has a couple of approaches that work. The problem statement boils down to finding a subset of banknotes such that their sum is exactly equal to a certain value. Now, this problem is somewhat similar to the knapsack problem which asks for ways to fill up a knapsack of a certain size optimally with the given blocks. There is a solution based on dynamic programming for this problem, but we will be taking up a solution which makes good use of the way integers are represented in binary to solve this problem.

Now, the limit on the number of banknotes is ‘n’. Let us see how many subsets exist for these banknotes. For finding the number of subsets, we see that for every banknote, we have two choices, either to choose it in our calculation for the sum of notes or to ignore it in calculating the sum. Thus, we have 2 options per banknote and ‘n’ banknotes. So, the total number of subsets thus becomes 2^n where ^ represents the power operation. The number of subsets are small enough for us to bruteforce through them and the program to run in time.

An interesting way to generate all subsets of ‘n’ objects when ‘n’ is considerably small (n <= 20) is to use the properties of how unsigned integers are stored. Consider the number 2^n. This number is represented in binary form as ‘10000…0’, that is, 1 followed by n 0s. Also, any number containing a 1 at the same position will surely be greater than 2^n. Thus, all numbers below 2^n do not have a 1 in a position greater than or equal to ‘n’ starting from the LSB. By induction, we can do the same for values of n = n-1 and n-2 and so on. Thus, we can see that any number between 2^(n-1) and 2^n will have a 1 in the position n-1. Extending this logic, we can say that if we consider the numbers from 1 to 2^n, we would be considering all possible ways in which we can choose some objects from ‘n’ objects.

For example, consider n = 3, so 2^n = 8. Let us list ‘i’ and its binary representation
i    Binary representation using ‘n’ bits
0    000
1    001
2    010
3    011
4    100
5    101
6    110
7    111

As you can see, if we consider that 1 means that we have selected object at that position and 0 means that we have not selected the object at that position, we can get all possible subsets of ‘n’ objects by looping over numbers from 1 to 2^n.

For calculating the sum of the subset represented by ‘i’, we loop from 0 to ‘n’ and we check whether the corresponding bit is set in the value for ‘i’ or not. If it is, we include that object in calculating our sum else we don’t. In this way, we can get the sum for all possible subsets of the ‘n’ objects.

This is exactly what we need for this problem. After taking in the number of objects, we loop ‘i’ from 1 to 2^n incrementing the value of ‘i’ by 1 at every stage to give us a new subset. Then for a particular value of ‘i’, we loop ‘j’ from 0 to n and check if the bit at that particular value is set or not. Languages like C / C++ provide bit-wise operators for leftshift and rightshift. For checking if the bit is set at position ‘j'(starting from 0) we can just check if the value of (i & (1<<j)) is 0. If it is 0, then the bit is not set, while if it is greater than 0, then the bit is set. Alternatively, we can also loop from 0 to n and at each stage check whether ‘i’ modulo 2 is equal to 1 or not. If it is 1, then the bit at that position is set, else it’s not. Then we divide ‘i’ by 2 and proceed. At the end of the ‘n’ iterations, ‘i’ will equal 0. The problem with this appraoch is that the modulo operations take much more time compared to the bitwise operations. Thus, now that we know how to check if the bit is set, we initialize a value ‘sum’ equal to 0 at the start of the ‘n’ iterations for a value of ‘i’ and if the bit at position ‘j’ is set, we add the corresponding banknote value to ‘sum’ else we don’t. At the end of these iterations, we check if the value of ‘sum’ equals the required value. If it does, then we have found a subset with the required sum and so we print a “Yes” and exit. Else, if at the end of 2^n iterations of ‘i’ we don’t have a subset with the required sum, then we print a “No” and exit.

The program should look something like this :

`Start`
`Take in the value of 'n' and the required value of sum 'm'`
`Take in all the values for the banknotes in array 'd[]'`
`For i = 1 and i < (2^n)`
`    sum = 0`
`    For j = 0 and j < n`
`        if jth bit of i is set`
`            sum = sum + d[j]`
`    if sum equals m`
`        print Yes and return`
`Print No and return`

## India Wins Four Medals At IOI 2020

The 32nd International Olympiads in Informatics 2020 final results are out. All the four finalists from India are bringing back a medal each! A defining... debanjan321

## How Amit Upadhyay got placed at Cleartax

At CodeChef, we constantly stay in touch with CCDSAP holders to make the experience better for you and to fine-tune the certification. We spoke... admin

## ACM ICPC Kolkata Regionals 2016 – Live Updates

Welcome to ACM ICPC Kolkata Regional 2016, the last leg regional before the India Final! Animesh and I will be giving you live updates throughout...  wittyceaser

## 48 Replies to “Tutorial for problem “Paying Up””

1. German says:

Good tutorials always are welcome, but the code template doesn’t appear clear on Firefox 3.5 (it happened the same with the before tutorial.

It’s easy what I may do to see it right, however I think it’s a usability problem that should be fixed easily (w/CSS).

Kind Regards

German

1. swetantkumar says:

def search(k,m):
start=0
end=len(k)-1
res=-1
while start<=end:
mid=start+(end-start)//2
if k[mid]==m:
return m
elif k[mid]0:
t=search(k,m)
if t==-1:
break
k.remove(t)
sum=sum+t
m=m-t
if sum==r:
print(“Yes”)
else:
print(“No”)

Why it is not correct

2. German says:

Good tutorials always are welcome, but the code template doesn’t appear clear on Firefox 3.5 (it happened the same with the before tutorial.

It’s easy what I may do to see it right, however I think it’s a usability problem that should be fixed easily (w/CSS).

Kind Regards

German

3. pushkar says:

code appears properly on safari

4. pushkar says:

code appears properly on safari

5. The Chef says:

This is fixed. Thanks for pointing it out.

6. The Chef says:

This is fixed. Thanks for pointing it out.

7. RM says:

thanks 4 d tutorial…itz helpin newbies like me 2 get 2 kno better ways….pls keep on postim more!!!

8. RM says:

thanks 4 d tutorial…itz helpin newbies like me 2 get 2 kno better ways….pls keep on postim more!!!

9. Ankush says:

Gr8 one sir! ! !

10. Ankush says:

Gr8 one sir! ! !

11. nishant says:

Thanks a lot for tutorials.Its like a guide to newbies for getting accustomed to the problems…
keep posting them.
regards..

12. nishant says:

Thanks a lot for tutorials.Its like a guide to newbies for getting accustomed to the problems…
keep posting them.
regards..

13. shivam gupta says:

I have another solution for this problem……
We can find all possible additions and store it in another array and compare the sum with each element

Let me give u an example…..
lets have 3 banknotes as 2,4,7 so possible combinations are 2,4,6,7,9,11,13 which we will store in another array

here is the algo for it

1.Start

2.Accept the value of n and m

3.Accept all values of banknotes in an array a[]

4.declare an array b[] having first element initialised as 0 i.e. b=0

5.set flag=0 and top=0
//here top is used as continuous insertion of
//elements in b[] and flag is used to add all
//elements in b[] with a new banknote and store
//it further in b[]

6.for i=0 till i<n incremented each time by 1

7. for j=0 till j<=flag incremented each time by 1

8. top=top+1 , b[top]=a[i]+b[j]

9. flag=top

10.Now compare each element of b[] with m and print
yes if search is successful otherwise no

11.End

The above algo can be modified depending upon the problem…….

1. Mohd Imran says:

this is awesome solution..thanks,man

2. Krishna Kumar says:

Awesome solution

3. priyansh_34 says:

please suggest what is incorrect in my code because it is returning all correct outputs corresponding to given inputs but on submitting it returns wrong answer.
#include
#include

using namespace std;

int main()
{
int t,n,m;
cin>>t;
while(t–){
cin>>n>>m;
int x=m;
int a[n];
for(int i=0;i>a[i];
int sum=0;
sort(a,a+n);

for(int i=n-1;i>=0;i–)
{
if(a[i]<=x)
{sum+=a[i];
x=x-a[i];

}
if(sum==m)
break;

}
if(sum==m)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;

}
return 0;
}

14. shivam gupta says:

I have another solution for this problem……
We can find all possible additions and store it in another array and compare the sum with each element

Let me give u an example…..
lets have 3 banknotes as 2,4,7 so possible combinations are 2,4,6,7,9,11,13 which we will store in another array

here is the algo for it

1.Start

2.Accept the value of n and m

3.Accept all values of banknotes in an array a[]

4.declare an array b[] having first element initialised as 0 i.e. b=0

5.set flag=0 and top=0
//here top is used as continuous insertion of
//elements in b[] and flag is used to add all
//elements in b[] with a new banknote and store
//it further in b[]

6.for i=0 till i<n incremented each time by 1

7. for j=0 till j<=flag incremented each time by 1

8. top=top+1 , b[top]=a[i]+b[j]

9. flag=top

10.Now compare each element of b[] with m and print
yes if search is successful otherwise no

11.End

The above algo can be modified depending upon the problem…….

15. shivam gupta says:

i forgot to add that step 8 is inside inner for and step 9 is inside outer for i.e.
step 6
{
step 7
{
step 8
}
step 9
}

16. shivam gupta says:

i forgot to add that step 8 is inside inner for and step 9 is inside outer for i.e.
step 6
{
step 7
{
step 8
}
step 9
}

17. Aniruddha says:

Please don’t post code in the comments section on the blog. Post your doubts on the problem page and not here.

18. vijit dhingra says:

in case where n=20, a loop from i=1 till i<(2^20) takes too much time, doesn't it?

1. Soumya Ranjan Swain says:

2^20 is approx 10^6, so it will pass within 1 sec … 🙂

1. TEJA POLISETTY says:

2^20 is approx 10^6 . how u can say

1. Nilabja Bhattacharya says:

becuase 2^32 is less than 10^9

2. Aravind Gopal says:

And there are 100 testcases as well..

19. dungeon_master says:

import java.util.Scanner;

class Immutable{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while(t– > 0){
int n = s.nextInt();
int m = s.nextInt();
int[] arr = new int[n];
for(int i = 0;i < n; i++){
arr[i] = s.nextInt();
}
int i = 0;
for( ; i < (int)Math.pow(2, n); i++){
int sum = 0;
String check = Integer.toBinaryString(i);
for(int j = 0;j = (int)Math.pow(2, n))
System.out.println(“No”);
}
}
}

Instead of checking the bit using the shift operator, I am doing it by first converting the number i to a binary String and then iterating each character of the string and if the character is ‘1’ I am adding it to the sum….this program shows correct output for the sample case but it shows WA..can anyone please tell what is the flaw in this method….

20. Anamika Varshney says:

I am not getting the logic behind including the object in the sum based on the decision that corresponding bit for ‘i’ is set or not. It will be really kind if someone explain me that

1. Mohd Imran says:

1st banknote is assigned to LSB (let’s say) ,2nd note assigned to 2nd bit from left and so on..the logic is , in order to consider all the subsets that can be formed using these ‘n’ banknotes ,they are assigned to some bit in the n-bit number and we’ll iterate from 1 to 2^n . Now, if ‘i’th bit is set implies we’ll consider the corresponding banknote in our subset and add it to our sum.

Hope this clearifies..

1. Viren Negi says:

@disqus_iZPpYTsCbQ:disqus @samjoearmy:disqus Can you explain with a example. The example in the post is too vague for me to understand at this point.

2. Samjoe Army says:

Think of it as a binary number. If we have 3 elements, then think of numbers as: 000, 001, 010 , 011, 100, 101, 111 these are the only 2^3 possibilities. Now we make a subset of elements where the number is set at 1. So actually we took care of all subsets. Combinatorially, each place in array has either to come in the subset or not. So two possibilites for every N. Thus a total of 2^N.

21. kashish joshi says:

I think the logic is correct as per the editorial.
#include

#include

int main() {

int t,n,m,i,a,s,j,b,c;

scanf(“%d”,&t);

while(t–)

{

scanf(“%d%d”,&n,&m);

for(i=0;i<n;i++)

scanf("%d",&a[i]);

b=pow(2,n);

c=0;

for(j=0;j>=1;

i++;

}

if(s==m)

{

c=1; break;

}

}

if(c)

printf(“yesn”);

else

printf(“non”);

}

return 0;

}

22. Phillion says:

while reading inputs there is no point in reading > m and == 0. some optimization. 🙂 nice problem though.

23. shubham says:

Can someone please explain me the meaning of the statement
i & (1<<j)

24. piyush says:

n=6 m=8
1,2,9,11,13,22,25
i have used some different logic max test cases are passing except the above one….

#include
#include

int main()
{
int t,n,m,a,k,i,j,temp,flag,flag1;
scanf(“%d”,&t);
while(t>=1)
{
scanf(“%d”,&n);
scanf(“%d”,&m);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
k=1;
while(k<=n-1)
{
for(j=0;ja[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
k++;

}

flag=m;

while(flag>0)

{
for(i=0;iflag)
{flag1=0;

break;

}
else if(a[i]==flag)
{

flag1 =flag;
break;
}

else
{

flag1=0;
c++;}
}
if (flag1!=0)
{
printf(“YES”);
break;
}

if(c==1)
{
if(flag!=a[c-1])
{

printf(“NOn”);
break;

}
else
{

printf(“YESn”);
break;

}
}
else if (c==0&&a!=flag)
{

printf(“NO”);

break;}
else

{

flag=flag-a[c-1];

}

}
t–;

}
return 0;
}

25. Simrit Singh says:

while(t>0){
int n,m,j;
cin>>n>>m;
int a[n];
for(int i=0;i>a[i];
sort(a,a+n,greater());
int sum=0;
for(j=0;jm)
continue;
if(a[j]==m)
{
cout<<"Yes"<<endl;
break;
}
else if(a[j]<m)
{
m=m-a[j];
}
}
if(j==n)
cout<<"No"<<endl;
t–;
}

why my code shows wrong answer ,passed all given test cases !!

26. Kunnu Singh says:

What it means by saying “if jth bit of i is set?? Can someone please explain

1. Bhavesh Gupta says:

is set maens it is 1 or selected.

27. Shivansh Sharma says:

Please tell me why I am getting wrong answer ? This code passed all sample test cases

import sys
def pay():
n, total = map(int,raw_input().split())
notes = []
for j in range(n):
x = input()
if(x>total):
continue
else:
notes.append(x)

notes.sort(reverse = True)

for k in xrange(len(notes)):
summ = notes[k]
for m in xrange(k+1,len(notes)):
if(summ>total):
summ -= notes[m-1]
summ += notes[m]

else:
summ += notes[m]
if(summ==total):
return ‘Yes’

return ‘No’

t = input()
for i in range(t):
y = pay()
print y

28. Viren Negi says:

Can Someone please explain me the Example

For example, consider n = 3, so 2^n = 8. Let us list ‘i’ and its binary representation
i Binary representation using ‘n’ bits
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

As you can see, if we consider that 1 means that we have selected object at that position and 0 means that we have not selected the object at that position, we can get all possible subsets of ‘n’ objects by looping over numbers from 1 to 2^n.

What are the 2 subset the Post is mentioning over here.

I’m not able to figure out which subset will it form my assumption is

(000, 001, 010, 011) and (100, 101, 110, 111) based on n(i.e) position value.

is that correct ?

If I’m correcting woudn’t that be slower then comparing directly with n < 3

29. Bhavesh Gupta says:

#include
int main()
{
int t;
scanf(“%d”,&t);
while(t–)
{

int n,sum,i,flag,t;
x:
scanf(“%d %d”,&n,&sum);
int a[n];
for(i=0;i<n;i++)
{

scanf("%d",&a[i]);
}
if(sum==0){printf("Yesn");
goto x;}
flag=0;
while(flag==0)
{
flag=1;
for(i=0;ia[i+1])
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
flag=0;
}
}
}
for(i=n-1;i>=0;i–)
{
if(sum-a[i]>=0)
{

if(sum-a[i]>0)
{
sum=sum-a[i];
}
else{printf(“Yesn”);
flag=0;
break;}
}
}
if(flag!=0)
printf(“Non”);
}
return 0;
}

30. Sabat Ullah says:

#include
#define ll long int
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
ll m;
cin>>n>>m;
int a[n];
for(int i=0;i>a[i];
}
int flag=0;
for(int i=1;i<(pow(2,n));i++)
{
ll sum=0;
for(int j=0;j<n;j++)
{
if(((i)&(1<<j))==1)
{
sum+=a[j];
}

}
if(sum==m)
{
flag=1;break;
}
}
if(flag==1)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
return 0;
}

31. shagun khaitan says:

why is this program giving wrong answer

#include
using namespace std;

char f(int a,int no,int n);
void generatesubsets(int a,int n,int k);
int main()
{
int t;
cin>>t;
while(t>0)
{
int n,k;
cin>>n>>k;
int a[n];
for ( int i=0;i>a[i];
generatesubsets(a,n,k);

t–;
}

return 0;
}

void generatesubsets(int a,int n,int k)
{
int range=(1<<n)-1;
char c='n';
for( int i=0;i<=range;i++)
{ c=f(a,i,k);
if(c=='y')
break;}
if(c=='y')
cout<<"Yes"<<endl;
else cout<<"No"<0)
{
if(no&1)
x+=a[i];
i++;
no=no>>1;
}
if(x==k)
{
return(‘y’);

}

}

32. Simran Gujrati says:

I have used dp to solve this problem
But getting TLE error
Any idea whats wrong in this?

#include
using namespace std;
int main() {
unsigned int T,N,s,i,j;
cin>>T;
while(T–)
{
cin>>N>>s;
unsigned int A[N];
for(i=0;i>A[i];

bool dp[N+1][s+1];

for(i=0;i<=N;i++)
dp[i]=true;

for(i=0;i<=s;i++)
{

dp[i]=false;

}

for(i=1;i<=N;i++)
{
for(j=1;j<=s;j++)
{
if(j<A[i-1])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=dp[i-1][j] || dp[i-1][j-A[i-1]];

}
}
if(dp[N][s])
cout<<"Yesn";
else
cout<<"Non";
}
return 0;
}

1. Nikhil Agrawal says:

I got same error if you got then plz tell .

33. Mudra Suthar says:

thanks

34. aniket says:

my code is correct and output getting also correct ,though i get wrong answer,why?

t=int(input())
for s in range(t):
n,m=map(int,input().split())
lst=[]
for i in range(n):
x=int(input())
lst.append(x)
l=len(lst)
import itertools

def subset(lst,l):
v=[]
for i in range(1,l+1):
lt=list(map(list,itertools.combinations(lst,i)))
v.extend(lt)
return v
k=0
for i in subset(lst,l):
sum=0
for j in i:
sum+=j
if(sum==m):
k=1
break
if(k==1):
print(‘yes’)
else:
print(‘no’)

35. sxdhun says:

#include

using namespace std;

bool subset_sum(int arr[], int sum, int n){
bool dp[n+1][sum+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<sum+1;j++){
if(i == 0)
dp[i][j] = false;

if(j == 0)
dp[i][j] = true;
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<sum+1;j++){
if(arr[i-1] >test;
while(test–){
cin>>n;
cin>>sum;
int arr[n];
for(int i=0;i>arr[i];
bool check;
check = subset_sum(arr, sum, n);
if(check == true)
cout<<"yes"<<"\n";
else
cout<<"no"<<"\n";
}
}

this is my dp solution . it passed all the example test cases but still got wrong answer when submited. idk what is the error !