Количество уникальных простых чисел, образованных удалением цифр данного числа

Опубликовано: 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 )

РЕКОМЕНДУЕМЫЕ СТАТЬИ