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
#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;
}