Максимально возможное простое число из подпоследовательности двоичной строки

Для данной двоичной строки задача состоит в том, чтобы найти максимально возможное простое число с помощью десятичного представления подпоследовательности данной двоичной строки. Если простое число не может быть получено, выведите -1 .

Примеры:

Input: S = “1001”
Output: 5 
Explanation: Out of all subsequences of the string “1001”, the largest prime number that can be obtained is “101” (= 5).

Input: “1011”
Output: 11 
Explanation: Out of all subsequences of the string “1011”, the largest prime number that can be obtained is “1011” (= 11).

Подход: Чтобы решить проблему, идея состоит в том, чтобы сгенерировать все возможные подпоследовательности строки и преобразовать каждую подпоследовательность в эквивалентную десятичную форму. Выведите наибольшее простое число, полученное из этой подпоследовательности.

Выполните следующие шаги, чтобы решить эту проблему:

• Инициализируйте вектор пар, скажем, vec, для хранения пар строк и их эквивалентных десятичных значений в Pair.first и Pair.second соответственно.
• Инициализируйте переменную, скажем, ans, для хранения требуемого ответа.
• Повторить цикл от i = 0 до длины строки s:
  • Повторить цикл от j = 0 до длины vec:
    • Сохраните j ^-ю пару в temp.
    • Если i -й символ строки s равен '1 ':
      • Добавьте символ в temp.first.
      • Обновите значение temp.second , сдвинув текущее значение влево и добавив к нему 1 .
    • В противном случае:
      • Добавьте символ в temp.first.
      • Обновите значение temp.second , сдвинув текущее значение влево и добавив к нему 0 .
    • Сохраните эту временную пару в vec .
    • Если temp.second простое:
      • Сохраните максимум ответов и temp.second в ответах .
  • Если ответ равен 0 :
    • Из строки s нельзя получить простое число.
  • В противном случае:
    • Распечатать ответ .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(2 ^N * √N), где N — длина строки.
Вспомогательное пространство: O(2 ^N * N)