a和b之间总数，其中包含用于至少一个零 [英] Total numbers between a and b which contains atleast one zero

问题描述

如何找到a和b（含）之间的数字的计数，其中包含0作为它们的数字。我不能够得到这与我在code使用下面的想法，就变得非常复杂的情况下前导零

How to find count of numbers between a and b (inclusive) which contains 0 as their digit. I am not able to get this with the idea which i have used below in my code, it becomes very complex in case of leading zeroes

为前如果= 1，B = 200总数应该是29，但我得到39。

for ex if a=1 and b=200 total number should be 29 but i am getting 39.

任何人都可以提出这样做​​的有效途径？

Can anyone suggest an efficient way of doing it?

约束：

1<=a<=b<=10^17

code：

code:

long long int F(long long int dig, long long int a, long long int num)
{
    if(dig == 0) {
        if(a>0)
            return 1;
        else
            return 0;
    }
    if(mem[dig][a])
        return D[dig][a];
    mem[dig][a] = 1;
    long long int ret = 0;
    for(long long int i = 0;i<=9;i++) {
        if(i==num)
            ret=(ret+F(dig-1,a+1,num));
        else
            ret=(ret+F(dig-1,a,num));
    }
    D[dig][a] = ret;
    return ret;
}

long long int solve(long long int x,long long int num)
{
    char cad[100];
    long long int ret = 0;
    long long int a=0,b=0,c=0,j;

    sprintf(cad,"%lld",x);
    int len = strlen(cad);
    long long int qued = len;
    for(long long int i = 0;i < len;i++) {
        qued--;
        long long int d = cad[i] - '0';
        for(j=0;j <d;j++) {
            if(j==num) {
                if(num==0 && i==0)
                    a=a+0;
                else
                    a=a+1;
                ret=(ret+F(qued,a,num));
            }
            else
                ret=(ret+F(qued,a,num));
        }
        if(d==num)
            a=a+1;
    }
    return ret;
}

解决方案 - >解决（B + 1,0）-solve（一，0）

solution is -> solve(b+1,0)-solve(a,0)

但我得到这个错误的答案

but i am getting wrong answer with this

我从中得到了上述思想的链接是的http：// codeforces。 COM /博客/项/ 8221

the link from which i got the above idea is http://codeforces.com/blog/entry/8221

推荐答案

一个简单的方法来做到这一点是：

A Simple way to do it would be:

    inList = [1, 2, ... n]
    outList = []
    for i in inList:
            for j in len(i):
                    if i%10 || i==0:
                        //there is a 0
                        outList.add(i)
                        break;
                    if(i<10)
                        //i cannot contain a 0
                        break;
                    i=i/10

Probibly唯一带正整数的作品，但它的琐碎占negitive号码。

Probibly only works with positive ints, but its trivial to account for negitive numbers.

根据您的约束简单而有效的O（10N）或O（17N）

Simple and efficient O(10N) or O(17N) according to your constraints

这篇关于a和b之间总数，其中包含用于至少一个零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！