[digital statistics DP] counting problem

subject

338. Counting problem - AcWing Question bank  

AcWing 338. Counting problem - AcWing

explain

• count Function to find from (1,num) Numbers （0-9） Number of occurrences
• If interval is required (a,b), Is equivalent to from the prefix and count The result of the difference in
• about num=abcdefg( Consider as follows ） Be careful x=0 Special circumstances of
• 

Code segment

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int get_num(vector<int>num,int l,int r)
{
    int n=0;
    for(int i=r;i>=l;i--)
    n=n*10+num[i];
    return n;
}
int power10(int x)
{
    int ans=1;
    while(x--)
    {
        ans*=10;
    }
        
        return ans;
}
int count(int n,int x)
{
    vector<int>num;
    while(n)
    {
        num.push_back(n%10);
        n/=10;
    }
    n =num.size();
    int ans=0;
    for(int i=n-1-!x;i>=0;i--)
    {
        if(i<n-1)
        {
            ans+=get_num(num,i+1,n-1)*power10(i);
            if(!x)ans-=power10(i);
            
        }
        if(num[i]==x)ans+=get_num(num,0,i-1)+1;
        else if(num[i]>x)ans+=power10(i);
    }
    return ans;
}
int main()
{
    int a,b;
    while(cin>>a>>b,a)
    {
        if(a>b)
        swap(a,b);
        for(int i=0;i<10;i++)
        cout<<count(b,i)-count(a-1,i)<<' ';
        cout<<endl;
    }
    return 0;
}