| 12 | ll dp[11][2][2];//we only need to check if the number formed contains 3 or not so for that we only take flag to tell that |
| 13 | |
| 14 | ll g(string s,ll pos=0,ll flag=0,ll tight=1 ){ |
| 15 | if(pos==s.length()){//always when we have formed s.size elements we |
| 16 | if(flag)return 1; |
| 17 | else return 0; |
| 18 | } |
| 19 | //cout<<pos<<" "<<flag<<" "<<tight<<endl; |
| 20 | if(dp[pos][flag][tight]!=-1){ |
| 21 | return dp[pos][flag][tight]; |
| 22 | } |
| 23 | else if(tight==1){ |
| 24 | ll tot=0;//inti. with 0 because every pos.is decided with the number then next pos. trace the sum for that |
| 25 | for(int i=0;i<=s[pos]-'0';i++){ |
| 26 | ll flg=flag;//this imp. that for every position i have to new flag variable and pass it because if 3 appeared once and i made the main variable 1 then for further positions all flag will be 1. |
| 27 | if(i==3)flg=1; |
| 28 | if(i==s[pos]-'0'){ //uss particular index par boundary value aaigi toh aage type |
| 29 | tot+=g(s,pos+1,flg,1); |
| 30 | } |
| 31 | else{ |
| 32 | tot+=g(s,pos+1,flg,0); |
| 33 | } |
| 34 | } |
| 35 | return dp[pos][flag][tight]=tot; |
| 36 | } |
| 37 | else{ |
| 38 | ll tot=0; |
| 39 | for(int i=0;i<=9;i++){ |
| 40 | ll flg=flag; |
| 41 | if(i==3)flg=1; |
| 42 | tot+=g(s,pos+1,flg,0); |
| 43 | } |
| 44 | return dp[pos][flag][tight]=tot; |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | |
| 49 | |