aaravaki2125's blog

A nice Digit Dp Problem (Solved)
By aaravaki2125, history, 3 years ago, In English

So I came across this question in my interview round and only 4/11 of my test cases are passing due to high constraints. The Problem goes like this -

We are given two no L and R . And we need to tell the count of numbers who are even freq numbers. (even freq numbers are those numbers if the no of occurrences of each digit is even for example-2222,516165 and 888888445353. and 11220 is not an even free no.)

Constraints — 0<=L<R<=10^18 (huge constraint)

**input- L=1 R=40

ans=3 (11,22,33)

I have tried using a map but it fails I know it can be done using digit DP please someone help me solve this problem.

Here is my map Code-

bool ifpos(ll n) {
    unordered_map<int,int>mp;
    
    while(n!=0){
        mp[n%10]++;
        n/=10;
    }
	
    for(auto it:mp){
        if(it.second%2==1)
        return false;
    }
    return true;
}

bool ifeven(ll n)
{
    int count=0;

    while(n!=0){  
        n/=10;
        count++;
    }
	
    if(count%2==0)
    return true;
	
    return false;    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll l,r;
    cin>>l>>r;
    ll ans=0;
    for(int i=l;i<=r;i++)
    {
        if(ifpos(i) and ifeven(i)){
        ans++;
        debug(i);
        }
    }
    cout<<ans<<endl;

    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It can be easily solved with a standard digit DP solution with a bitmask as an extra state parameter. The mask can denote the nature (even/odd) of the frequency of each character.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Ask yourself, while placing the digit at the ith position (measured from left) what do you need to know?

1) Whether the number built so far is surely lesser than R or not(the "tight condition")? (This affects the choice of your current digit)

2) How many digits placed have even parity (remaining digits will have odd parity).?

3) Which position are you at currently.?

That's it! It's simple now, take dp[i][mask][tight] as the no. of numbers <=R starting from pos i to last pos where mask is a 10 bit binary number denoting the partiy of count of digit (from pos i to last pos). Just place all valid digits and use the dp state with the corosponding bit at mask flipped, and you're done!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally I have completed this code thanks @zenolus and @ShivanshJ for guiding me towards the solution.

string a, b;
ll dp[20][2][2][(1 << 11)]; // 18 is the max length of digit 10^18 so took 20 | 2 for tight or not | 0000000000  <- 10 bits
//                                                                       0123456789
ll findans(string &num, ll tight, ll index, ll nst, ll mask)
{
    if (index == num.size())
    {
        return (mask == 0 and nst==0);
    }
    if (dp[index][tight][nst][mask] != -1)
    {
        return dp[index][tight][nst][mask];
    }

    ll end = tight ? num[index] - '0' : 9;

    ll ret = 0;
    for (ll i = 0; i <= end; i++)
    {
        ret += findans(num, tight && (i == end), index + 1, nst && (i == 0), (i == 0 and nst == 1) ? 0 : mask ^ (1 << i) );
    }

    return dp[index][tight][nst][mask] = ret;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

     ll t;
    cin >> t;

    while (t--)
    {
        cin >> a >> b;

       // ll at =  stoi(a);
        //ll bt = stoi(b);

        ll ans = 0;
        memset(dp, -1, sizeof dp);
        ans = findans(b, 1, 0, 1, 0);

        //cout << ans << endl;

        memset(dp, -1, sizeof dp);
        ans = ans - findans(a, 1, 0, 1, 0);

        //cout << ans << endl;

        // check for a
        map<int, int>m;
        for (ll i = 0; i < a.size(); i++)
        {
            m[a[i] - '0']++;
        }

        ll ok = 1;
        for (auto i : m)
        {
            if (i.ss % 2) // digit freq of occurence is not even
            {
                ok = 0;
                break;
            }
        }

        if (ok)
        {
            // cout<<"\n++\n";
            ans++;
        }

        cout << ans << endl;

    }
    return 0;
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good work! I see this often that people like to follow this analogy of a function's answer over a range [L, R] = f([0, R]) — f([0, L-1]). However, I feel this other approach is much more intuitive to understand. We simply extend the concept of tight. Just like we use a tight condition for the higher end, we can simply use a tight for the lower end.

    Hope this code helps in understanding that. I have used an extra state parameter called "started". This is used here in order to root out the answers where we are considering the initial 0s to be a part of the solution, which they should not be considered as.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

include <bits/stdc++.h>

define int long long

using namespace std;

int fun(int i,int c,vector v,int bit) { if(i==v.size()) //if we are at last position { if(bit==0) //if frequency of all elements are even return 1; else
return 0; }

int ans=0; if(c) //if we need to fill position under some condition { for(int k=0;k<v[i];k++)
ans+=fun(i+1,0,v,bit ^ (1<<k));

ans+=fun(i+1,1,v,bit ^ (1<<v[i]));

}

else { for(int k=0;k<=9;k++) ans+=fun(i+1,0,v,bit ^ (1<<k)); }

return ans; }

int count(int n) { vector v;//vector to store digits of the number while(n) { v.push_back(n%10); n=n/10; } reverse(v.begin(),v.end()); if(v.size()%2==0) return fun(0,1,v,0)-1; //if the number of digits is even then 0000 will also be included so we need to subtarct it return fun(0,1,v,0); }

int32_t main() { int l,r; cin>>r>>l;

cout<<count(r)-count(l)<<endl;

return 0; }

→ Reply