UniLecs #Task. Number of natural numbers
Published in
2 min readMay 17, 2020
Задача: необходимо написать алгоритм для поиска натуральных чисел от 1 до 10^n, все цифры в которых различны.
Входные данные: n — натуральное число
Вывод: кол-во искомых чисел
Пример:
1. n = 1; Output = 9
2. n = 2; Output = 90
Разбор
Очевидно, что если число состоит как минимум из 11 цифр и более, то оно обязательно содержит хотя бы 2 одинаковые цифры. Значит для N>10 результат будет таким же как и для N = 10.
Рассматриваем числа на промежутке от 1 до 10^n, которые состоят из однозначных, 2х значных, 3х значных, … n-значных чисел.
Частные случаи:
- N = 1, кол-во однозначных чисел равно 9 (от 1 до 9).
- N = 2, кол-во 2х-значных чисел равно 9*9 = 81 (цифру десятков выбираем 9ю способами от 1 до 9, цифру единиц — также 9ю способами от 0 до 9 и одна цифра уже использована в десятках).
- N = 3, кол-во 3х-значных чисел всего 9*9*8 = 648 (цифра сотен — 9 способов, цифра десятков — 9 способов, цифра единиц — 8 способов).
Кол-во i-значных чисел будет (где 1 < i <= 10):
9 * 9 * 8 * 7 * … * (11 — i)
Реализация
https://gist.github.com/unilecs/b630236d50042492771b1cd1f3d6c94c
