//给定数字N，计算从1~N中各个数字位上包含1的个位

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
using namespace std;
//方法1，暴力穷举,一个数需要o(logn),一共需要n*O(logn)
int NumberOf1(unsigned int n){
    int number=0;
    while(n){//从个位往高位计算给定的数字n包含的数字1的个数
        if(n%10==1)
            number++;

        n=n/10;
    }
    return  number;
}
int NumberOf1Between1AndN(unsigned int n){
    int number=0;
    for(int i=1;i<=n;i++)
        number+=NumberOf1(i);
    return number;
}
//方法二，递归
//数字转换为 字符串更方便//递归一次去掉一位，所以时间复杂度编程O(logn)
int PowerBase10(unsigned int n){
    int result=1;
    for(unsigned int i=0;i<n;i++)
        result*=10;
    return result;
}
int NumberOf1(const char* strN){
    if(!strN||*strN<'0'||*strN>'9'||*strN=='\0')
        return 0;
    int first=*strN-'0';
    unsigned int length=static_cast<unsigned int>(strlen(strN));
    if(length==1&&first==0)
        return 0;
    if(length==1&& first>0)
        return 1;
    //假设strN="21345"
    //numberFirstDigit是数字10000~19999的第一个位中的数目
    int numFirstDigit=0;
    if(first>1)
        numFirstDigit=PowerBase10(length-1);
    else if(first==1)
        numFirstDigit=atoi(strN+1)+1;
    //numberOtherDigits是1346~21346除第一位之外的数位中的数目
    int numOtherDigits=first*(length-1)*PowerBase10(length-2);
    //numRecursive是1~1345中的数目
    int numRecursive=NumberOf1(strN+1);
    return numFirstDigit+numOtherDigits+numRecursive;
}

int NumberOf1Between1AndN(int n){
    if(n<=0)
        return 0;
    char strN[50];
    sprintf(strN,"%d",n);
    return NumberOf1(strN);
}

int main()
{
    cout<<NumberOf1Between1AndN(21345);
    //cout<<PowerBase10(2);
    return 0;
}