A nice Digit Dp Problem (Unsolved)

Revision en1, by aaravaki2125, 2021-08-23 01:37:18

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;
}
Tags digit dp, #3d-dp, maps

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English aaravaki2125 2021-08-24 05:04:23 4
en1 English aaravaki2125 2021-08-23 01:37:18 1390 Initial revision (published)