Уменьшите данный массив [1, N], вращая влево или вправо в зависимости от заданных условий.

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

Учитывая отсортированный массив arr[] первых N натуральных чисел и целое число X , задача состоит в том, чтобы напечатать последний оставшийся элемент после выполнения следующих операций (N – 1) раз:

  • Если значение X равно 1 , то поверните массив вправо на 1 единицу и удалите последний элемент.
  • Если значение X равно 2 , то поверните массив влево на 1 единицу и удалите первый элемент.

Примеры:

Input: N = 5, arr[] = {1, 2, 3, 4, 5}, X = 1
Output: 3
Explanation:
The operations are performed as follows:

  1. Rotating the array right by 1 unit modifies the array to {5, 1, 2, 3, 4}. Deleting the array element modifies the array to {5, 1, 2, 3}.
  2. Rotating the array right by 1 unit modifies the array to {3, 5, 1, 2}. Deleting the array element modifies the array to {3, 5, 1}.
  3. Rotating the array right by 1 unit modifies the array to {1, 3, 5}. Deleting the array element modifies the array to {1, 3}.
  4. Rotating the array right by 1 unit modifies the array to {3, 1}. Deleting the array element modifies the array to {3}.

Therefore, the last remaining element is 3.

Input: N = 5, arr[] = {1, 2, 3, 4, 5}, X = 2
Output: 3

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы поместить все числа диапазона [1, N] в адек и выполнить заданные операции (N – 1) раз в соответствии с заданным значением X , а затем вывести последнее оставшийся элемент.

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

Эффективный подход. Данная задача может быть оптимизирована на основе следующих наблюдений:

  1. Если значение X равно 1 , то последним оставшимся элементом будет разница между наименьшей степенью 2 и большей N. и Н .
  2. Если значение X равно 2 , то последний левый элемент будет 2*(N – D) + 1, где D представляет наибольшую степень числа 2, меньшую или равную N.

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

  • Сохраните степень двойки, большую, чем N, в переменной, скажем, nextPower.
  • Если значение X равно 1 , то в качестве результата выведите значение (nextPower – N) .
  • В противном случае в качестве результата выведите значение 2*(N – nextPower / 2) + 1 .

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

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

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