Блог

Я пытаюсь найти эффективный метод подсчета количества натуральных чисел, меньших или равных определенному числу 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)
  

Вам приходится очень тяжело разбирать число и считать цифры. Давайте упростим эти шаги. Учитывая целое число num , получите отдельные цифры, а затем найдите уникальные цифры:

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

Теперь, если уникальных цифр меньше, чем длина исходного числа, у вас есть повторение.

Я надеюсь, что вы можете справиться с кодированием отсюда.

Я действительно думаю, что реализация этого не будет стоить того, если вы не пытаетесь делать это много раз. Если это для практики, я думаю, что знание о перестановках может быть полезным.

Как насчет использования перестановок и комбинаций. Видите ли, с помощью перестановок вы можете подсчитать количество способов упорядочения определенной группы цифр с повторением или без него.

Хорошо, во-первых, каждое число выше 10 разрядов имеет повторяющийся номер. Таким образом, вы можете пропустить подсчет всего, что превышает 9 999 999 999

Перестановка может дать вам количество способов, которыми группа не имеет повторяющихся чисел. Используя это и простое вычитание, вы можете найти то, что хотите. (вам нужно будет сделать это для каждого значения места, единицы, десятков, сотен …) (Также вам придется исключить те, которые начинаются с 0, с другой перестановкой)

Теперь проблема в том, что он может считать только те, у которых есть только 9. Например, 9999, потому что он учитывает все возможности. допустим, у вас есть 3999, для этого вам нужно будет посчитать последние 3 цифры, без 3 в группе перестановок. Затем добавьте перестановку с повторением с уже включенным 3. Затем повторите для 2999, 1999 и добавьте возможности для 999. Рассуждения следующие:

• если у вас уже есть 3 в первой цифре, если она появляется снова, повторяется. Так что, если вы посчитаете перестановки без 3. Затем вы можете просто сложить все перестановки, которые включают как минимум 3.

С таким числом, как 3244, вам просто нужно применить то же самое для 244…

Я знаю, что это не совсем простое решение, и оно может сбивать с толку, но это может сократить вашу задачу для чего-то вроде log (n) .

Удачи 🙂

Вы можете искать перестановки в Google, это довольно распространенная вещь в математике.

Я бы попытался аналитически определить соответствие числа и использовать это значение для вычисления конечного результата.

Рассмотрим (для, 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