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:)
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.
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
Which is non zero …Hence its set…
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…
Yeah No Problem!!