Hi all I am trying this problem using digit dp approach though I have not applied memoization yet but my recursive backtrack is not working appropriately . please help me to figure out where is the problem

**Problem**

```
#include<iostream>
#define ll long long
using namespace std;
ll n;
ll x=0;
ll solve(ll index, ll small, ll last){
if(index==x)
return 0;
ll ans=0;
if(small){
ll ans1=solve(index+1,small,0);
ll ans2=solve(index+1,small,1);
if(last==1) ans2++;
ans=ans1+ans2;
}
else{
if((n&(1<<(x-index-1)))!=0){
ll ans1=solve(index+1, 1, 0);
ll ans2=solve(index+1, 0, 1);
if(last==1) ans2++;
ans=ans1+ans2;
}
else{
ans=solve(index+1, 0, 0);
}
}
return ans;
}
int main(){
ll t;
cin>>t;
while(t--){
cin>>n;
ll cpy = n;
x=0;
while(cpy>0){
x++;
cpy/=2;
}
cout<<solve(0,0,0)<<"\n";
}
return 0;
}
```

Auto comment: topic has been updated by taklo (previous revision, new revision, compare).Suppose n = 15 and you are in the state

`solve(1, 0, 1)`

, i.e. you have this number`1???`

, then if you put in the current index a`1`

(`11??`

) you get a new adjacent bit for all the following possibilities, it means that you need to add to all the remaining valid possibilities this new adjacent bit, that in this case is`2^2`

and not just one. The code working will be:I recommend adding another parameter that is accumulative of adjacent bits in the current number, and when the

`index`

is equal to`x`

instead to return`0`

return the accumulator.Thanks sir got my mistake

Auto comment: topic has been updated by taklo (previous revision, new revision, compare).