Сколько существует чисел в интервале без дубликатов цифр

@SupremeEP · Регистрация: 01.12.2015

Студворк — интернет-сервис помощи студентам

Есть интервал [l, r], 1 <= l < r <= 10^18.

Условие - отсутствие дублированных цифр:
101 - имеет две 1 - не подходит;
123 - не имеет дублированный цифр - подходит.

Требуется найти количество подходящих чисел в интервале от l до r. Хотелось бы объяснения

От 1 до 10, есть 10 чисел.
От 1 до 100 есть 90 чисел.

Байт · 07.09.2016, 17:48

Если число имеет более 10 цифр, то без дублирования - никак
Для r < 10¹¹ задача сводится к генерации(подсчету) перестановок из k элементов + генерации (подсчету) сочетаний С₁₀^k

@Peoples · 07.09.2016, 17:56

Не уверен в правильности работы с большими числами

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include<algorithm>
using namespace std;
bool f(string s) {
    int f=0;
    for(size_t i=0; i!=s.length(); i++)
        if(count(s.begin(),s.end(),s[i])>1) {
            f++;
        } 
        if(f>0){
            return true;
        } else return false;
}
int main() {
    int l,r;
    int c;
    cin>>l>>r;
    char buffer [20];
    for(int i=l; i<=r; i++) {
        itoa(i,buffer,10);
        if(!f(buffer)) {
            c++;
        }
    }
    cout<<c;
    return 0;
}

Байт · 07.09.2016, 21:16

Peoples, Вы думаете, что счетчик инициализировать не надо?

Добавлено через 1 минуту
Да, конечно перебор ВСЕХ чисел из диапазона даст ответ. Но
а. Это чудовищно неэффективно
б. Это неинтересно.

@Peoples · 07.09.2016, 21:22

Сообщение от Байт

счетчик инициализировать не надо

Спасибо, проморгал, когда писал

Сообщение от Байт

Это неинтересно.

Так оно и есть

Сообщение от Байт

чудовищно неэффективно

А почему так не эффективно?

Байт · 07.09.2016, 21:52

Сообщение от Peoples

А почему так не эффективно?

Для примера возьмем количество цифр 10. Всего чисел (которые вы перебираете) 10¹⁰ = 10000000000. Но с разными цифрами всего 10! = 3628800 < 4*10⁶. Разница на 3-4 порядка

Добавлено через 7 минут

Сообщение от Peoples

Так оно и есть

А устройство перебора всех перестановок из 10 цифр делает задачу чуточку интереснее. Не говоря уже о том, что если цифр меньше 10, нужно привлечь генерацию или подсчет сочетаний (биномиальных коэффициентов).
Кроме того, по значениям границ l и r можно понять, какие цифры не должны начинать число. Это дает уменьшение перебора не на порядок, а всего лишь в несколько раз, но уже может представить интерес, как упражнение для досужего ума

IGPIGP · 07.09.2016, 22:08

У-упс, не вычитал условие. del.

@SupremeEP · 09.09.2016, 23:53 **[ТС]**

G(n) - количество н-значных "правильных" чисел.
G(n) = 9 * Г(11-n+(n-1)) / Г(11-n) = 9 * 9! / (10-n)!

R(l, r) - функция, которая даёт ответ.
G(n) = R(10^(n-1), 10^n-1), при n > 1.
R(l,r) = R(l, r1) + R(r1+1, r2) + (r2+1, r3) + ...

Как всё это связать - не представляю

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 05.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 17.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@SupremeEP 4 / 4 / 2 Регистрация: 01.12.2015 Сообщений: 36

	Сколько существует чисел в интервале без дубликатов цифр 07.09.2016, 16:38. Показов 1378. Ответов 7 Метки интервал, комбинаторика, числа (Все метки) Есть интервал [l, r], 1 <= l < r <= 10^18. Условие - отсутствие дублированных цифр: 101 - имеет две 1 - не подходит; 123 - не имеет дублированный цифр - подходит. Требуется найти количество подходящих чисел в интервале от l до r. Хотелось бы объяснения От 1 до 10, есть 10 чисел. От 1 до 100 есть 90 чисел. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	07.09.2016, 17:48
	Если число имеет более 10 цифр, то без дублирования - никак Для r < 10¹¹ задача сводится к генерации(подсчету) перестановок из k элементов + генерации (подсчету) сочетаний С₁₀^k 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	07.09.2016, 21:16
	Peoples, Вы думаете, что счетчик инициализировать не надо? Добавлено через 1 минуту Да, конечно перебор ВСЕХ чисел из диапазона даст ответ. Но а. Это чудовищно неэффективно б. Это неинтересно. 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4706 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	07.09.2016, 22:08
	У-упс, не вычитал условие. del. 0

@SupremeEP 4 / 4 / 2 Регистрация: 01.12.2015 Сообщений: 36
	09.09.2016, 23:53 [ТС]
	G(n) - количество н-значных "правильных" чисел. G(n) = 9 * Г(11-n+(n-1)) / Г(11-n) = 9 * 9! / (10-n)! R(l, r) - функция, которая даёт ответ. G(n) = R(10^(n-1), 10^n-1), при n > 1. R(l,r) = R(l, r1) + R(r1+1, r2) + (r2+1, r3) + ... Как всё это связать - не представляю 0