Сложность: hard
Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.
Пример:
Input: digits = ["1","3","5","7"], n = 100
Output: 20
👨💻 Алгоритм:
1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.
2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.
3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.
😎 Решение:
def atMostNGivenDigitSet(digits, n):
n_str = str(n)
n_len = len(n_str)
digits = sorted(digits)
def count_less_than_equal(prefix, digits, n_str):
if len(prefix) == len(n_str):
return 1 if prefix <= n_str else 0
total = 0
for d in digits:
if prefix + d <= n_str[:len(prefix) + 1]:
total += count_less_than_equal(prefix + d, digits, n_str)
else:
break
return total
total_count = 0
for i in range(1, n_len):
total_count += len(digits) ** i
total_count += count_less_than_equal("", digits, n_str)
return total_count
Ставь 👍 и забирай 📚 Базу знаний