Проверьте, можно ли сделать данный массив перестановкой от 1 до N, уменьшив элементы вдвое

Учитывая массив nums[] размера N , задача состоит в том, чтобы проверить, может ли данный массив быть преобразован в перестановку от 1 до N после выполнения заданных операций любое количество раз (может быть 0). Операция определяется как: выберите любой элемент массива, скажем , «x» , и замените его на «x/2» .

Примечание. В перестановке от 1 до N все числа в диапазоне [1, N] присутствуют в любом порядке, и каждое число присутствует только один раз.

Примеры:

Input: N = 4, nums[] = {1, 8, 25, 2}
Output: true
Explanation: Sequence of operations followed are listed below:
Replace 8 with 8/2 = 4, nums[] = {1, 4, 25, 2}
Replace 25 with 25/2 = 12, nums[] = {1, 4, 12, 2}
Replace 12 with 12/2 = 6, nums[] = {1, 4, 6, 2}
Replace 6 with 6/2 = 3, nums[] = {1, 4, 3, 2} (Here element from 1 to 4 is present exactly once)

Input: N = 4, nums[] = {24, 7, 16, 7}
Output: false

Подход: Решение задачи основано на сортировке. Создайте массив freq логического типа и размера (N+1) , чтобы отслеживать числа желаемой перестановки. Выполните следующие шаги:

• Отсортируйте заданный массив.
• Обход с задней части массива и на каждом шаге:
  • Если val меньше N , а freq[val] ложно , пометьте его как true.
  • Если val больше N или freq[val] истинно , разделите его на 2, тогда как (val > 0 && freq[val] == true)
  • Наконец, проверьте, достигнута ли желаемая перестановка или нет.

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

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