help in digit dp problem

Revision en1, by taklo, 2020-03-29 20:26:47

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English taklo 2020-03-30 07:07:51 10
en2 English taklo 2020-03-29 21:06:27 1012
en1 English taklo 2020-03-29 20:26:47 1017 Initial revision (published)