计算至少有一个重复的数字的有效方法

Question

我试图找到一种有效的方法来计算小于或等于某个数字x的正整数的数量，这个数字至少有一个重复的数字。

我试图数一数有重复数字的数字，然后从x中减去它，但是我的程序对于x到10^10来说太慢了。

我搜索并找到了两种方法来实现这个想法：

def count_unique(x): 
    cnt = 0
    for i in range (x + 1): 
        num = i
        visited = [0,0,0,0,0,0,0,0,0,0]
        while (num): 
            if visited[num % 10] == 1: 
                break
            visited[num % 10] = 1 
            num = (int)(num / 10)
        if num == 0: 
            cnt += 1
    return cnt -1
for i in range(int(input())):
    x = int(input())
    print(x - count_unique(x))

以及：

Prefix = [0] 
def repeated_digit(n): 
    a = [] 
    while n != 0: 
        d = n%10
        if d in a: 
            return 0
        a.append(d) 
        n = n//10
    return 1
def pre_calculation(MAX): 
    global Prefix 
    Prefix.append(repeated_digit(1)) 
    for i in range(2,MAX+1): 
        Prefix.append(repeated_digit(i)+Prefix[i-1]) 
MAX = 10000000000
pre_calculation(MAX) 
for i in range(int(input())):
    x = int(input())
    print(x - Prefix[x])

但不幸的是，它们都不够快，有谁有更好的方法来实现这一点吗？

样本输入：

2    #number of test cases
10
20

样本输出：（每个测试用例的结果）

0   #no number less than 10 with a repeating digit
1   #one number less than 20 with a repeating digit (which is 11)

Answer 1

我会试图分析找出这个数字的恭维值，并使用这个值来计算最终结果。

考虑（for， N=请求输入）：

1. X = #positive-integers with all unique digits
2. Create the algo to figure out X
3. Final result = N - X

这是我的工作代码：

def all_unique_numbers_with_n_digits(d: int):
    if d < 1:
        return 0
    count = 9
    dig = 9
    while d > 1:
        count *= dig
        dig -= 1
        d -= 1
    return count


def count_numbers_with_unique_digits_less_than_n(n: int):
    X = str(n)
    count = 0

    unique_digs = set(range(9))

    for i in range(1, len(X)+1):
        # print("i,", i, X)
        dig_value = int(X[i-1])
        dv = dig_value if i == len(X) else dig_value-1
        # print(X, i, dig_value, dig_multiplier, count)
        count += max(dv, 0) * all_unique_numbers_with_n_digits(len(X)-i)
        if dig_value in unique_digs:
            unique_digs.remove(dig_value)
        if i != len(X):
            count += all_unique_numbers_with_n_digits(len(X)-i)
        else:
            mval = 0
            for x in unique_digs:
                if dv >= x > mval:
                    mval = x
            count += mval

    return count


def numbers_with_atleast_1_dig_repeating(n: int):
    return n - count_unique(n)


print(count_numbers_with_unique_digits_less_than_n(9))
print(count_numbers_with_unique_digits_less_than_n(100))
print(count_numbers_with_unique_digits_less_than_n(101))

输出：

90
90
90

Answer 2

我真的认为，除非你多次尝试，否则实现这一点是不值得的。如果是为了练习，我认为了解排列是有用的。

使用排列和组合怎么样？你看，通过排列，你可以计算你可以排列某一组数字的方式，有或没有重复。

好的，首先，每一个超过10度的数字，都有一个重复的数字。所以你可以跳过9999999999以上的数字

排列可以为您提供一组没有重复数字的计数方式。使用这个和一个简单的减法，你可以找到你想要的。（您必须为每个位置值、单位、十、百……）执行此操作）（此外，您还必须使用另一个置换来消除以0开头的那些）

现在，问题是它只能精确地计算那些只有9的。例如9999，因为它计算所有的可能性。假设你有一个3999，为此你必须计算最后3位数的可能性，而置换组中没有3。然后添加已包含3的重复排列。然后重复2999,1999，并添加999的可能性。推理如下：

• 如果第一个数字中已经有一个3，如果再次出现则重复。所以如果你计算没有3的排列。然后你可以把所有的排列加起来，至少包括一个3。

对于像3244这样的数字，你只需要对244应用同样的东西...

我知道这不是一个简单的解决方案，它可能会让人困惑，但它可以减少您的任务，比如log（n）。

祝你好运：）

你可以在谷歌上搜索关于排列的信息，这在数学中很常见。

Answer 3

要解构数字和数数数字，你要经历很多痛苦。让我们简化这些步骤。给定一个整数num，获取各个数字，然后找到唯一的数字：

digits = str(num)
unique_digits = set(digits)

现在，如果唯一数字的长度小于原始数字的长度，则有一个重复。

我相信你可以从这里处理编码。