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.
yaa i thought of that but it didnt work may be theres some issue with code i will check that
please check this code
`#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;
}`
was this a ques of kickstart round h??
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
ok great!!!