I just learned the basics of the binary system, but am still struggling to implement this in Java for Paying Up. Looked at other problems and still not understanding the basics. These are only 3 digits in this tutorial example  isn't this a byte? and aren't bytes composed of 8 digits? Also what is really happening when "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" Below is my basic code with just the input taken care of  I'd really appreciate help figuring out where and how to represent the problem in binary. Thanks, public class Main {
} asked 06 Jul '14, 14:20

The concept used in the tutorial is bitmasking. It is similar to having a visited array where 1 represents the value is present in the set and 0 represents its not present. E.g. if bitmask = 1011 in binary The bit at position 0,1,and 3 are 1. So it means 0,1 & 3rd term are in d set. 1 << j = j th bit as 1 (j th item in the set) So (i & 1 << j) != 0 means the j th bit of i is also 1. (i & 1 << j) != 0 implies j th item is in the set 'i' So as per tutorial: we iterate i from 0 to 2^n (all possible sets) Then check if j th item is present (( i & 1 << j) != 0) if present add it to sum Once you have checked for all j values if sum = demand print Yes If non of the sum is equal to demand print No answered 06 Jul '14, 21:15

You can look at this Wonderful tutorial.If you have any doubts, comment below. answered 06 Jul '14, 16:39

I don't know much java but let me help you with the basic idea if I understood your problem right! Correct me if I am wrong. This type of implementation helps when the input is small(so that 2^n is not large). This situation arises when you have to select items from a collection which will yield a definite sum or something else. For example in this problem you have to select the notes from your wallet which will sum up to certain number. If there 3 items, 110 means you included the first and second items and excluded the third one. You can also look at the link given above (Wonderful Tutorial), it gives a detailed explanation. Hope this helps! answered 06 Jul '14, 16:48

Thank you everyone for the help; I understand how it works now and submitted a detailed solution in Java ( http://www.codechef.com/viewsolution/4238701 ) for anyone who was curious. answered 07 Jul '14, 02:55
