Getting wrong answer for test case A : 75 B : 22


#1

TEST CASE
A : 75
B : 22

int n;
int dp[2][100005][101];
int solve1(int tight,string s, int val,int sum,int idx) {
int ans = 0;
int mod = 1000000007;
if(idx>=n){
if(val == sum) return 1;
else return 0;
} else {
if(dp[tight][val][idx] !=-1) {
return dp[tight][val][idx];
}
if(tight) {
for(int i=0;i<=s[idx]-‘0’;i++) {
if(idx == 0 && i==0) continue;
if(i==s[idx]-‘0’){
ans +=solve1(1,s,val+i,sum,idx+1);
ans %=mod;
if(ans<0){
ans +=mod;
ans %=mod;
}
} else {
ans +=solve1(0,s,val+i,sum,idx+1);
ans %=mod;
if(ans<0){
ans +=mod;
ans %=mod;
}

            }
        }
    } else {
                 for(int i=0;i<=9;i++) 
                ans +=solve1(0,s,val+i,sum,idx+1); 
                                     ans %=mod;
                                      if(ans<0){
                                         ans +=mod;
                                         ans %=mod;
                                     }

            
    }
}
 if(ans<0){
                                         ans +=mod;
                                         ans %=mod;
                                     }
                     ans %=mod;


return dp[tight][val][idx] = ans;

}
int Solution::solve(int A, int B) {
string s ="";
memset(dp,-1,sizeof dp);
for(int i=0;i<A;i++) s+=‘9’;
//cout<<s<<endl;
n = s.size();
return solve1(1,s,0,B,0);

}


#2

I think this should work

ans = (ans%mod + solve1(0,s,val+i,sum,idx+1)%mod)%mod