PROBLEM LINK:
Author: Adarsh Kumar Sinha
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Dynamic Programming.
EXPLANATION:
Subtask 1:
For lower constraints a single loop will do the work. Just iterate through each integers from L+1 to R, and check if the number of set bits in the number formed the sum of the digits is $>=$$3$.
Solution for subtask 1
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int t;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while(t--){
ll a,b;
cin >> a >> b;
int ans=0;
for(ll i=a+1; i<=b; i++){
s = to_string(i);
ll sum = 0;
for(ll j=0; j<s.size(); j++){
sum += (s[j]-'0');
}
ll cnt;
cnt = __builtin_popcount(sum);
if(cnt>=3){
ans++;
}
}
cout << ans << endl;
}
}
Subtask 2:
For bigger constraints on L and R, O(n) will however will give a TLE verdict. For this a better approach is to use the concept of Digit-DP. The implementation we have used in the eeditorial is a recursive one.
DP[200][2][20] is the DP state we are using here. Where the first parenthesis of [200] denotes the sum obtained during the particular recursive call. The second parenthesis of [2] denotes the ‘tight’ of the recursive call. In a typical Digit-DP implementation, if tight is true, this means we are constrained to use only digits less than or equal to original digit at that particular position. The third [20] denotes the possible position, that is the current position in the original integer while generating the new integer.
The base case is simple. When we’ve reached the end of the length of the original integer, we will be having the ‘sum’ of the digits while generating the integer. Hence we check if the number of set bits are >= 3 or not.
We do this process twice. First covering the range 0 to R. Second covering the range 0 to L. Hence when we subtract these two, we get the answer which is in the range L+1 to R, which is the required answer.
Solution
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
ll l,r;
ll dp[200][2][20];
ll solve(ll tight, string s, ll sum, ll pos){
if(pos==s.size()){
ll cnt;
cnt = __builtin_popcount(sum);
if(cnt>=3){
return 1;
}
return 0;
}
if(dp[sum][tight][pos]!=-1){
return dp[sum][tight][pos];
}
ll res=0;
if(tight){
for(ll i=0; i<=s[pos]-'0'; i++){
if(i==s[pos]-'0'){
res += solve(1, s, sum+i, pos+1);
}
else{
res += solve(0, s, sum+i, pos+1);
}
}
}
else{
for(ll i=0; i<=9; i++){
res += solve(0,s,sum+i,pos+1);
}
}
return dp[sum][tight][pos]=res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
cin >> l >> r;
string s;
ll sum=0;
s = to_string(l);
memset(dp,-1,sizeof(dp));
string num(s.size(),'0');
ll ans1 = solve(1,s,sum,0);
memset(dp,-1,sizeof(dp));
string num2(s.size(),'0');
s = to_string(r);
ll ans2 = solve(1,s,sum,0);
cout << ans2 - ans1 << endl;
}
}