Uber | OA Coding Questions and Solutions | Set - 2 | 2022

Question

Given a string of length  , n .

It contains either '?' or a digit from '0' to '9'.

Find the number of possible good strings.

Good strings are numbers which leave remainder 7 when divided by 11 and 13.

1<=n<=10000

Example input 1 :

??756

Output : 1

Only 1 good string is possible which is 34756

Example input 2 :

??33?

Output : 10

Some of the possible strings are : {   42335 , 46339 } . There are 8 more strings which are good strings , i.e , they leave remainder 7 when divided by 11 and 13 individually.

Answer 1

The solution involves dynamic programming(multi-dimensional). Here is my code for the same :----->

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
ll dp[15][15][10000+5] ; 
ll e = 1e9 + 7 ; 
int main() 
{
    string s ;
    cin>>s ; 
    ll n = s.size() ; 
    dp[0][0][0] = 1 ; 
    ll i = 1 ; 
    while(i<=n)
    {
        if(s[i-1]=='?')
        {
            ll number = 0 ; 
            while(number<=9)
            {
            ll i1 = 0 ; 
            while(i1<=10){
                ll j1 = 0 ;
                while(j1<=12)
                {
                ll x1 = ( (i1%11*10%11)%11 + number%11)%11;
                ll y1 = ( (j1%13*10%13)%13 + number%13)%13;
                dp[x1][y1][i] = (dp[x1][y1][i] + dp[i1][j1][i-1])%e   ;  
                j1++;
                }
                i1++;
            }
            number++;
            }
        }
        else
        {
        ll number = int(s[i-1])-48;
        ll i1 = 0 ; 
        while(i1<=10)
        {
            ll j1 = 0 ;
            while(j1<=12)
            {
                ll x1 = ( (i1%11*10%11)%11 + number%11)%11;
                ll y1 = ( (j1%13*10%13)%13 + number%13)%13;
                dp[x1][y1][i] = (dp[x1][y1][i] + dp[i1][j1][i-1])%e   ;  
                j1++;
            }
            i1++;
        }
        }
        i++;
    }
     cout<<dp[7][7][n];
    return 0 ; 
}