Incredible Hulk Problem

#1

why counting only the set-bits gives the result?

#2

Hey @tasfikrahman007 , in this problem it is mentioned that hulk can only jump in the power of 2 i.e in one jump hulk can jump 1,2,4,8,16,32,64… levels
so now coming to test cases
for n=4
since 4 is already in power of 2 so hulk can jump once covering 4 levels thus ans=1
for n=5
hulk has to jump twice i,e in one jump it crosses 4 levels and in another it crosses 1

Hence set bits give the same as required in the question .

In case of any doubt feel free to ask :slight_smile:
mark your doubt as resolved if your query got resolved

#3

Why we are counting set bits
Assume we have 20
Now for minimum jumps we will take 16 and 4
So that means for minimum jumps we will always take max power of 2 <n we can take and reduce it from our no ,so in terms of bits it means removing left most bit

Now lets see bit representation of 20 its (1100) here 3rd left bit have a value 4 and last bit have a value 16
So (1100) -> we take 16 out ->(0100)->we take 4 out ->(0000)
Now I hope your doubt is cleared.

Incredible hulk