Перестановки заданного числа, являющиеся степенью двойки

Опубликовано: 22 Сентября, 2022

Для заданной строки S , состоящей из N цифр, задача состоит в том, чтобы напечатать все возможные комбинации цифр S , являющиеся полной степенью числа 2.

Примеры:

Input: S = “614”
Output: 4
Explanation:
All possible combinations of digit of S that are perfect power of 2 are 1, 4, 16, 64.

Input: S = “6”
Output: 0

Подход: Данная проблема может быть решена с помощью Backtracking. Идея состоит в том, чтобы сгенерировать все возможные перестановки строки S , если это совершенная степень числа 2, а затем вывести ее. Выполните следующие шаги, чтобы решить проблему:

  • Определите функцию check(int number) , чтобы проверить, является ли данное число степенью двойки , и выполните следующие задачи:
    • Если число равно 0, то вернуть false.
    • Если побитовое И числа и числа-1, затем вернуть true, иначе вернуть false.
  • Определите функцию calculate(int arr[], string an) и выполните следующие задачи:
    • Если длина строки an не равна 0 и значение функции. check(Integer.parseInt(ans.trim())) возвращает true, затем добавьте это значение в HashSet H[] .
    • Переберите диапазон [0, 10], используя переменную i , и выполните следующие задачи:
      • Если arr[i] равно 0 , то продолжаем.
      • В противном случае уменьшите значение arr[i] на 1 и вызовите функцию calculate(temp, «») , чтобы найти другие возможные перестановки строки str и добавить значение arr[i] на 1 .
  • Инициализируйте HashSet H[] для хранения возможных строковых чисел, которые являются степенью числа 2.
  • Инициализируйте массив, скажем, temp[] для хранения частот целых чисел в строке str .
  • Повторяйте цикл while до тех пор, пока N не станет равным 0 , и выполните следующие шаги:
    • Инициализируйте переменную rem как N%10 и увеличьте значение temp[rem] на 1 .
    • Разделите значение N на 10 .
  • Вызовите функцию calculate(temp, "") , чтобы найти возможные перестановки строки S.
  • После выполнения вышеуказанных шагов распечатайте HashSet в качестве результата.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O( N *9N)
Вспомогательное пространство: O(1)

Эффективный подход : идея состоит в том, чтобы изначально сгенерировать все степени двойки и сохранить их в соответствующей структуре данных (в данном случае «набор CPP») и проверить, выходит ли степень двойки в строке.

  • Трудность здесь заключается в том, чтобы проверить, есть ли степень двойки в строке.
  • наивный подход к проверке того, является ли мощность двух выходов в строке генерацией всех возможных перестановок строк и проверкой, является ли эта строка или строка имеет степень 2, этот подход не рекомендуется, поскольку временная сложность составляет около O (n!)
  • Эффективным подходом является использование массива count, в котором хранится количество десятичных цифр и проверка того, меньше или равно ли количество десятичных цифр степени 2 количеству десятичных цифр в строке.

СЛОЖНОСТЬ ВРЕМЕНИ: O (log (2 ^ 62) * N), где N — длина строки, а log (2 ^ 62), потому что 2 ^ 62 — максимальная допустимая мощность в диапазоне Long
ВСПОМОГАТЕЛЬНОЕ ПРОСТРАНСТВО:O(10+10)

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