Последний элемент массива после многократного удаления первого элемента и добавления его в конец массива дважды ровно K раз

Дан массив arr[] , состоящий из N целых чисел и положительного целого числа K , задача состоит в том, чтобы найти последний элемент, присутствующий в массиве, полученном путем многократного удаления первого элемента массива и добавления его дважды в конец массива K раз. .

Примеры:

Input: arr[] = {1, 2, 3, 4, 5}, K = 5
Output: 5
Explanation:
Initially, the array is {1, 2, 3, 4, 5}. Following operations are performed K(= 5) number of times:
After the 1^st operation, the array modifies to {2, 3, 4, 5, 1, 1}.
After the 2^nd operation, the array modifies to {3, 4, 5, 1, 1, 2, 2}.
After the 3^rd operation, the array modifies to {4, 5, 1, 1, 2, 2, 3, 3}.
After the 4^th operation, the array modifies to {5, 1, 1, 2, 2, 3, 3, 4, 4}.
After the 5^th operation, the array modifies to {1, 1, 2, 2, 3, 3, 4, 4, 5, 5}.
After completing the above operations, the last element is 5. Therefore, the answer is 5.

Input: arr[] = {1, 2, 3}, K = 7
Output: 2

Подход: Данную проблему можно решить, соблюдая следующую закономерность:

Consider an array arr[] = {1, 2, 3, 4, 5}
After first 5 operations, the array modifies to {1, 1, 2, 2, 3, 3, 4, 4, 5, 5}.
After first 10 operations, the array modifies to {1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5}.

Therefore, the size of the array after N * 2^K operations is 2 * N * 2^K.

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

• Итерируйте цикл со значения 0 , используя переменную j , и обновляйте значение K как (K – N * 2 ^j ) до тех пор, пока K не станет больше, чем N * 2 ^j .
• После выполнения вышеуказанных шагов инициализируйте переменную, скажем, r как 2 ^j , где каждое значение повторяется R раз.
• Инициализируйте переменную, скажем, M как 1 , которая хранит индекс символа в массиве arr[] , который равен последнему символу после выполнения K операций.
• Переберите диапазон [1, N], используя переменную i , и если значение K больше, чем R * i , затем увеличьте M на 1 .
• После выполнения вышеуказанных шагов выведите значение arr[M – 1] в качестве результирующего последнего элемента массива.

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

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