Given a range of integers i.e. [L,R] asks him to find the count of such integer i where L ≤ i ≤ R and binary representation of i contains the pattern 110 as a substring.
Can someone check why this code is wrong?
`#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define endl “\n”
#define fast_in_out ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int mod=1e7+9;
void input()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
}
int a,b;
string s;
int dp[70][70][70][2][2];
int f(int pos,int p1,int p2,bool found,bool tight)
{
if(pos == s.size())
{
return (found==1);
}
if(dp[pos][p1][p2][found][tight]!=-1)
{
return dp[pos][p1][p2][found][tight];
}
int res=0;
int ub = tight ? s[pos]-‘0’:1;
for(int i=0;i<=ub;i++)
{
int nt = tight;
if(i < ub)
{
nt = 0;
}
if(p1==1 && p2==1 && i==0)
{
res += f(pos+1,s[pos]-‘0’,p1,1,nt);
}
else
{
res += f(pos+1,s[pos]-‘0’,p1,0,nt);
}
}
return dp[pos][p1][p2][found][tight]=res;
}
string binary(int x)
{
string res;
while(x>0)
{
int rem = x%2;
res += to_string(rem);
x=x/2;
}
return res;
}
int solve(int x)
{
string str = binary(x);
reverse(str.begin(),str.end());
s=str;
//cout<<s<<endl;
memset(dp,-1,sizeof(dp));
int res=f(0,0,0,0,1);
return res;
}
int32_t main()
{
fast_in_out;
input();
int t;
cin>>t;
while(t–)
{
cin>>a>>b;
int ans = solve(b) - solve(a-1);
cout<<ans<<endl;
}
return 0;
}`