Binary Implementation of Paying Up

general
, , ,
1

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.
How do we look at/process the different ways 2^n where n=3 = 8 can be 0 0 0, 0 1 0 … etc.

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 {

public static void main(String[] args)throws java.io.IOException{

	java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
	java.io.BufferedWriter out = new java.io.BufferedWriter(new java.io.OutputStreamWriter(System.out)); 

	int tests = Integer.parseInt(reader.readLine());
	while(tests-->0){
		String[] params = reader.readLine().split(" ");
		int n = Integer.parseInt(params[0]); //quantity of different notes in wallet <= 20
		int m = Integer.parseInt(params[1]); //demanded amount $
		
		int[] noteValues = new int[n]; //store each distinct note
		for(int i = 0; i < n; i += 1)
			noteValues[i] = Integer.parseInt(reader.readLine());
		
		if(validSet(noteValues,m))
			out.write("Yes\r\n");
		else
			out.write("No\r\n");
	}
	out.flush();
}
/**check if a set of sorted notes can meet the exact demand.*/
public static boolean validSet(int[] notes, int demand){
	
	return false;
}

}

2

You can look at this Wonderful tutorial.If you have any doubts, comment below.

1 Like
3

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!

1 Like
4

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

2 Likes
5

thanks for the pointers, i’ve read this tutorial but i suppose this is my biggest confusion:
i understand if the person has 4 notes in his wallet, there are 2^4=16 different combinations of notes we can check to see if it meets the demand. but how are we converting all these numbers into binary?

what are we exactly looping? how is the array (of ints?) initialized? what is the data value type of “0 0 1 0” , i know this equals 2, but how do we know/make sure we are checking every combination?

ex. i would set it up like

for(int i = 1; i < Math.pow(2,n); i += 1){
  int sum = 0;
  for(int j = 0; j < n; j += 1){
    if bit is 1, add sum += corresponding note
  }
  if sum == demand, return true
}
return false

I just don’t know how to convert and check all these possible combinations into binary representations and loop them.

6

Thank you everyone for the help; I understand how it works now and submitted a detailed solution in Java ( CodeChef: Practical coding for everyone ) for anyone who was curious.

7

Just use int. Int has 32 bit which can represent 2^32 sets and each set is nothing but a unique number.

We dont convert numbers to binary they are already stored that way.We are using them as it is with the help of bitwise operators like (& |) and shift operators.

Your implementation is right. The variable ‘i’ represents the set. And to check if corresponding bit is 1 just use (i & 1<<j) != 0 and your code should work.

Also store the value of 2^n and then use it in loop to reduce run time.

1 Like