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 ↵
↵
<spoiler summary="Problem">↵
A bit is a binary digit, taking a logical value of either 1 or 0 (also referred to as "true" or "false" respectively). And every decimal number has a binary representation which is actually a series of bits. If a bit of a number is 1 and its next bit is also 1 then we can say that the number has a 1 adjacent bit. And you have to find out how many times this scenario occurs for all numbers up to N.↵
↵
Examples:↵
↵
Number Binary Adjacent Bits↵
↵
12 1100 1↵
↵
15 1111 3↵
↵
27 11011 2↵
↵
Input↵
Input starts with an integer T (≤ 10000), denoting the number of test cases.↵
↵
Each case contains an integer N (0 ≤ N < 231).↵
↵
Output↵
For each test case, print the case number and the summation of all adjacent bits from 0 to N.↵
</spoiler>↵
↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
please help me to figure out where is the problem ↵
↵
<spoiler summary="Problem">↵
A bit is a binary digit, taking a logical value of either 1 or 0 (also referred to as "true" or "false" respectively). And every decimal number has a binary representation which is actually a series of bits. If a bit of a number is 1 and its next bit is also 1 then we can say that the number has a 1 adjacent bit. And you have to find out how many times this scenario occurs for all numbers up to N.↵
↵
Examples:↵
↵
Number Binary Adjacent Bits↵
↵
12 1100 1↵
↵
15 1111 3↵
↵
27 11011 2↵
↵
Input↵
Input starts with an integer T (≤ 10000), denoting the number of test cases.↵
↵
Each case contains an integer N (0 ≤ N < 231).↵
↵
Output↵
For each test case, print the case number and the summation of all adjacent bits from 0 to N.↵
</spoiler>↵
↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
