Задача
Дано натуральное число [latex]N[/latex]. Сколько различных цифр встречается в его десятичной записи?
Входные данные
Натуральное число [latex]N[/latex].
Выходные данные
Количество различных цифр [latex]sum[/latex].
Тесты
| Входные данные | Выходные данные |
| [latex]N[/latex] | [latex]sum[/latex] |
| 12345678900987654321 | sum:10 |
| 302 | sum:3 |
Код программы с использованием deque
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <deque> using namespace std; int main(){ deque<int> folder; unsigned long long N; cin >> N; folder.push_back(N%10); N/=10; while (N!=0){ for (int i=0; i<folder.size(); i++){ if (folder.at(i) == N%10) i+=folder.size(); if (i == folder.size() -1) folder.push_back(N%10); } N/=10; } cout << "sum:" << folder.size(); return 0; } |
Решение
Создадим дэк [latex]folder[/latex] в котором будем хранить различные цифры десятичной записи. Добавляем первую цифру числа [latex]N[/latex] в дэк и делим [latex]N[/latex] на [latex]10[/latex]. Следующие цифры мы будем добавлять после проверки на отсутствие таких же в [latex]folder[/latex], если цифры совпадают заканчиваем цикл. В конце выводим размер [latex]folder[/latex] который и является [latex]sum[/latex].
Код программы с использованием массива
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; int main(){ int folder[10]={0}, sum=0; long long N; cin >> N; while (N!=0){ folder[N%10]++; N/=10; } for (int j=0; j<10; j++) if(folder[j]!=0) sum++; cout << "sum:" << sum; return 0; } |
Решение
Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].
Ссылки
Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).
Это неудачное решение. Каждую новую цифру Вы сравниваете с уже имеющимися. Это слишком долго. Да и выбор деки в качестве хранилища ничем не объяснён.
Хочу дать небольшую подсказку в форме вопроса. Сколько всего разных цифр может быть в числе?
Да! Именно это я и имел в виду.
Хорошо.
Если бы мы не знали что всего 10 вариантов, то нам нужно было бы использовать в качестве контейнера не массив, а что-то не допускающее повторов. Например, множество. В С++ это может быть контейнер set.