You are not logged in. Please login at to post your questions!


Binary Implementation of Paying Up

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.


public class Main {

public static void main(String[] args)throws{ reader = new; out = new;

    int tests = Integer.parseInt(reader.readLine());
        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());

/**check if a set of sorted notes can meet the exact demand.*/
public static boolean validSet(int[] notes, int demand){

    return false;


asked 06 Jul '14, 14:20

slaynen's gravatar image

accept rate: 0%

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

abbas's gravatar image

accept rate: 28%

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


answered 06 Jul '14, 16:39

achaitanyasai's gravatar image

accept rate: 10%

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

sunny210's gravatar image

accept rate: 0%

edited 06 Jul '14, 16:52

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.


answered 06 Jul '14, 21:43

slaynen's gravatar image

accept rate: 0%


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.

(07 Jul '14, 02:31) abbas4★

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


answered 07 Jul '14, 02:55

slaynen's gravatar image

accept rate: 0%

edited 07 Jul '14, 03:09

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 06 Jul '14, 14:20

question was seen: 1,167 times

last updated: 07 Jul '14, 03:09