Paying up:explaination

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

plz anyone explain how to implement

if jth bit of i is set----line of the above algorithm in a java code .

@zargus I think for “jth bit of i” means,

Consider i to be a binary number. cosisting of n bits ie 1,2…j…n;

It is talking about that j(some position in the number) in the binary representation of i.

“A bit is set” in terms of a binary number is simply to see if the value at that bit is 1 or not.

If value=1 bit is said to be “set”.

So if,

i=000- None of the bits are said to be set.

i=001- 3rd bit is said to be set(starting from left)

i=100- 1st bit is said to be set(Starting from left)

i=110- 1st and 2nd bit are said to be set

And coming to java, i don’t know if there’s a shortcut but you could find the actual binary representation (might be naive,very costly and give TLE) but in c/c++ there are bitwise operators available!

Hope this helps:)

2 Likes

To test if jth bit of i is set (in java):

int maxBit = 1<<i;
for(int j=0; j<maxBit; j++)
   if (( i && (1<<j) )>0) //testing if the jth bit of i is set
   {
      // Do something
   }

As you can see, java also has bitwise operators.

1 Like

To check if a the j-th bit of a number i is set,

we can see if ( i & 1 << j ) is non-zero.

(1 << j) means left shift …or in simple terms find 2^j.

To be precise if the bit is set, then the result would be 2^j.

This is because in the number 2^j there is only 1-bit and that is the j-th bit,

eg:2^1=2 Binary–>10 only "1"st bit is set(0 based from right)…(Set means bit is “1”)

if it’s ANDing with i results in a non-zero number then the j-th bit is set in i.

Anding --> a & b is 1 only wen both bit positions are 1…

Take an example:–>

To check if 3 rd bit of Number 11010 is set or not

find 2^3=8 Binary–>01000

Anding with that number itself
11010

01000

Anding we get
01000

Which is non zero …Hence its set…

Example 2)
Take same number.And find weather bit 2 is set or not
11010 && 2^2

–>
11010

00100

result is
00000

which is zero hence bit is not set(Reset)…

Using this concept u can easily code in java using bitwise operators…(& and << Bitwise operators)

Hope This helps…

2 Likes

@jaythegenius thnx a lot got an ac :)!!

Yeah No Problem!!

//