Уменьшите массив, заменив 1-й и средний элемент суммой и разностью попеременно.

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти последний оставшийся элемент массива после последовательного удаления 1 ^-го и среднего элемента массива и поочередного добавления их суммы и разности в конец массива.

Примеры:

Input: A = {2, 4, 1, 5, 7}
Output: 5
Explanation: During the 1st iteration, remove arr[0] and arr[2] from the array 
and append their sum (2 + 1 = 3) to the end of the array. 
Hence, arr[] = {4, 5, 7, 3}. 
Again repeat the same process and remove arr[0] and arr[2] from the array 
and now append their difference (7 – 4) = 3. 
Hence, arr[] = {5, 3, 3}.
 After the next iteration, array will become arr[] = {3, 8}. 
And finally after the last iteration, arr[] = {5} which is the last required value.

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Output: 15

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

• Поддерживайте переменную op , в которой хранится количество операций.
• Удалить первый и средний элемент массива, пока его размер не станет больше 1 , и дополнить массив их сложением или вычитанием в соответствии с операцией (т. е., если операция четная, выполнить сложение, иначе выполнить вычитание).

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

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