Количество уникальных простых чисел, образованных удалением цифр данного числа
Опубликовано: 22 Сентября, 2022
Для заданного числа N задача состоит в том, чтобы подсчитать количество уникальных простых чисел, которые можно получить, удалив ноль или более цифр данного числа.
Примеры:
Input: N = 132
Output: 3
Explanation:
The total prime numbers formed by deleting zero or more digits of the given number 132 are 3 i.e. [3, 2, 13].Input: N = 2222
Output: 1
Подход : эту проблему можно решить с помощью рекурсии, поскольку для каждой цифры есть два варианта: либо включать цифру, либо не включать цифру. Для каждого выбора проверьте, является ли образовавшееся число простым или нет. Выполните следующие шаги, чтобы решить эту проблему:
- Инициализируйте HashSet, скажем, Primes для хранения уникальных простых чисел.
- Объявите функцию, скажем, uniquePrimeNums(number, ans, index) , передавая числовую строку N, ans как пустую строку и индекс 0 в качестве параметров.
- Базовый случай: если индекс достигает длины строки, затем преобразуйте строку в целое число и проверьте, является ли сформированное число простым или нет, и если оно является простым, то добавьте число в HashSet Primes .
- Вызовите функцию uniquePrimeNums для обоих вариантов выбора, либо взяв символ, т.е. uniquePrimeNums(число, ответ + номер.charAt(индекс), индекс + 1) , либо оставив символ, т.е. уникальныйPrimeNums(номер, ответ, индекс + 1) .
- После выполнения вышеуказанных шагов выведите размер HashSet Primes в качестве требуемого ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(2 N * sqrt(N))
Вспомогательное пространство: O(2 N )