# Digit DP problem

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.

1 ≤ T ≤ 100 1 ≤ L ≤ R ≤ 10^18
Input :
3
5 16
20 50
1 100
Output:
4
15
48

Can someone help me in this??

Hoping you have some knowledge of digit dp.
So tackle the problem like this:

ans = count from 0 to R - count from 0 to L - 1

now you have a simple problem of counting the numbers from 0 to X which have the pattern 110

convert X to binary…
Instead of digits from 0 to 9 you have digits 0 and 1 only.
now this becomes a standard types.

dp states :
int idx = current bit that you want to place
int prev = previous bit
int prev2 = previous of previous bit
bool found = if pattern has been previously found or not
bool flag = just to see if the current number is smaller or not

so if prev2 == 1 and prev == 1 and current number placed is 0 , increment the count by 1 and solve for the next bits.
just try to take care of some other cases.

1 Like

yaa i thought of that but it didnt work may be theres some issue with code i will check that

`#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())
{
if(found==1)
{
return 1;
}
else
{
return 0;
}
}
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,pos,p1,1,nt);
}
else
{
res += f(pos+1,pos,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;
}`

No this was not from the kickstart round but yes the second problem was based on digit DP , atleast i solved it using digit dp I dont know about others

1 Like

ok great!!!